凸包算法(convex hull)
我想问如要找很多组的凸包该如何实现, 用C++。谢谢。例子：
输入
2（要找多少个）
5（第一个有5个坐标）
1 1
1 -1
00
-1 -1
-1 1
8（第二个有8个坐标）
10
01
0-1
-10
20
02
0-2
-20
输出
4（第一凸包由4个组成）
-1 -1
1 -1
1 1
-1 1
4（第二个凸包由4个组成）
-20
0-2
02
20 题解：#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.x < points.x) l = i;
int p = l, q;
do
{
hull.push_back(points);
q = (p+1)%n;
for (size_t i = 0; i < n; i++) if (orientation(points, points, points) == 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.x << ' ' << hull.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;
for(size_t i = 0; i < N; i++){
int x, y;
std::cin >> x >> y;
points.x = x;
points.y = y;
}
int n = sizeof(points)/sizeof(points);
convexHull(points, n);
}
return 0;
}输入/输出：2
5
1 1
1 -1
00
-1 -1
-1 1
Convex Hull: 4points
-1 -1
1 -1
1 1
-1 1
8
10
01
0-1
-10
20
02
0-2
-20
Convex Hull: 4points
-2 0
0 -2
2 0
0 2我知道可以用 using namespace std，但是我比较喜欢不用命名空间 兄弟，如果解答对你有帮助，请给最佳解答，谢谢
页:
[1]