[已解决]凸包算法(convex hull)

kkken · 发表于 2021-11-9 17:09:13

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

我想问如要找很多组的凸包该如何实现, 用C++。谢谢。
例子：
输入
2（要找多少个）
5（第一个有5个坐标）
1 1
1 -1
0  0
-1 -1
-1 1
8（第二个有8个坐标）
1  0
0  1
0  -1
-1  0
2  0
0  2
0  -2
-2  0
输出
4（第一凸包由4个组成）
-1 -1
1 -1
1 1
-1 1
4（第二个凸包由4个组成）
-2  0
0  -2
0  2
2  0

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2021-11-12 22:08:10

题解：

#include <bits/stdc++.h>
struct Point{int x, y;};
int orientation(Point p, Point q, Point r)
{
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0;
return (val > 0)? 1: 2;
}
void convexHull(Point points[], int n)
{
if (n < 3) return;
std::vector<Point> hull;
int l = 0;
for (size_t i = 1; i < n; i++) if (points[i].x < points[l].x) l = i;
int p = l, q;
do
{
hull.push_back(points[p]);
q = (p+1)%n;
for (size_t i = 0; i < n; i++) if (orientation(points[p], points[i], points[q]) == 2) q = i;
p = q;
} while (p != l);
std::cout << "\nConvex Hull: " << hull.size() << "points" << std::endl;
for (size_t i = 0; i < hull.size(); i++) std::cout << hull[i].x << ' ' << hull[i].y << std::endl;
std::cout << std::endl;
}
int main()
{
int N, T;
std::cin >> T;
for(size_t t = 0; t < T; t++){
std::cin >> N;
Point points[N];
for(size_t i = 0; i < N; i++){
int x, y;
std::cin >> x >> y;
points[i].x = x;
points[i].y = y;
}
int n = sizeof(points)/sizeof(points[0]);
convexHull(points, n);
}
return 0;
}

复制代码

输入/输出：

2
5
1 1
1 -1
0 0
-1 -1
-1 1
Convex Hull: 4points
-1 -1
1 -1
1 1
-1 1
8
1 0
0 1
0 -1
-1 0
2 0
0 2
0 -2
-2 0
Convex Hull: 4points
-2 0
0 -2
2 0
0 2

复制代码

我知道可以用 using namespace std，但是我比较喜欢不用命名空间

跳转到最佳答案楼层

傻眼貓咪 · 发表于 2021-11-12 22:08:10

题解：

#include <bits/stdc++.h>
struct Point{int x, y;};
int orientation(Point p, Point q, Point r)
{
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0;
return (val > 0)? 1: 2;
}
void convexHull(Point points[], int n)
{
if (n < 3) return;
std::vector<Point> hull;
int l = 0;
for (size_t i = 1; i < n; i++) if (points[i].x < points[l].x) l = i;
int p = l, q;
do
{
hull.push_back(points[p]);
q = (p+1)%n;
for (size_t i = 0; i < n; i++) if (orientation(points[p], points[i], points[q]) == 2) q = i;
p = q;
} while (p != l);
std::cout << "\nConvex Hull: " << hull.size() << "points" << std::endl;
for (size_t i = 0; i < hull.size(); i++) std::cout << hull[i].x << ' ' << hull[i].y << std::endl;
std::cout << std::endl;
}
int main()
{
int N, T;
std::cin >> T;
for(size_t t = 0; t < T; t++){
std::cin >> N;
Point points[N];
for(size_t i = 0; i < N; i++){
int x, y;
std::cin >> x >> y;
points[i].x = x;
points[i].y = y;
}
int n = sizeof(points)/sizeof(points[0]);
convexHull(points, n);
}
return 0;
}

复制代码

输入/输出：

2
5
1 1
1 -1
0 0
-1 -1
-1 1
Convex Hull: 4points
-1 -1
1 -1
1 1
-1 1
8
1 0
0 1
0 -1
-1 0
2 0
0 2
0 -2
-2 0
Convex Hull: 4points
-2 0
0 -2
2 0
0 2

复制代码

我知道可以用 using namespace std，但是我比较喜欢不用命名空间

傻眼貓咪 · 发表于 2021-11-12 22:18:38

兄弟，如果解答对你有帮助，请给最佳解答，谢谢

账号		自动登录	找回密码
密码			立即注册