凸包算法讲解:Click Herehtml
题目连接:https://vjudge.net/problem/POJ-1113ios
题意:简化下题意即求凸包的周长+2×PI×r。算法
思路:用graham求凸包,模板是kuangbin的,算法复杂度O(nlogn)。spa
AC code:.net
// Author : RioTian // Time : 20/10/21 #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> using namespace std; const int N = 1000; const double Pi = acos(-1.0); struct point { double x, y; point() : x(), y() {} point(int x, int y) : x(x), y(y) {} } list[N]; typedef point P; int stack[N], top; //计算叉积: p0p1 X p0p2 double cross(P p0, P p1, P p2) { return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y); } //计算 p1p2的 距离 double dis(P p1, P p2) { return sqrt((double)(p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y)); } //利用极角排序,角度相同则距离小排前面 bool cmp(P p1, P p2) { auto tmp = cross(list[0], p1, p2); if (tmp > 0) return true; else if (tmp == 0 && dis(list[0], p1) < dis(list[0], p2)) return true; else return false; } //输入,并把 最左下方的点放在 list[0] 。而且进行极角排序 void init(int n) { int i, k = 0; cin >> list[0].x >> list[0].y; P p0 = list[0]; // p0 等价于 tmp 去寻找最左下方的点 for (int i = 1; i < n; ++i) { cin >> list[i].x >> list[i].y; if (p0.y > list[i].y || (p0.y == list[i].y && p0.x > list[i].x)) p0 = list[i], k = i; } list[k] = list[0]; list[0] = p0; sort(list + 1, list + n, cmp); } //graham扫描法求凸包,凸包顶点存在stack栈中 //从栈底到栈顶一次是逆时针方向排列的 //若是要求凸包的一条边有2个以上的点 //那么要将while中的<=改为< //但这不能将最后一条边上的多个点保留 //由于排序时将距离近的点排在前面 //那么最后一条边上的点仅有距离最远的会被保留,其他的会被出栈 //因此最后一条边须要特判 //若是要求逆凸包的话须要改cmp,graham中的符号便可 void Graham(int n) { int i; if (n == 1) top = 0, stack[0] = 0; if (n == 2) top = 1, stack[0] = 0, stack[1] = 1; if (n > 2) { for (i = 0; i <= 1; i++) stack[i] = i; top = 1; for (i = 2; i < n; i++) { while (top > 0 && cross(list[stack[top - 1]], list[stack[top]], list[i]) <= 0) top--; top++; stack[top] = i; } } } int main() { freopen("in.txt", "r", stdin); // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int N, L; while (scanf("%d", &N) != EOF) { init(N); Graham(N); double res = 0; for (int i = 0; i < top; i++) res += dis(list[stack[i]], list[stack[i + 1]]); res += dis(list[stack[0]], list[stack[top]]); res += 2 * Pi; printf("%d\n", (int)(res + 0.5)); } }
题目连接:https://www.luogu.com.cn/problem/P2742code
题意:求凸包的周长。htm
思路:blog
这里用andrew算法来求,该算法与graham的区别是排序方法不同,这里按x坐标从左到右排序,x相同的按y坐标从下到上排序。下列程序展现先求下凸包,再求上凸包。复杂度O(nlogn),但听说比graham的复杂度小一点。排序
AC code:ci
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; const int maxn = 1e5 + 5; struct Point { double x, y; Point(double xx = 0, double yy = 0) : x(xx), y(yy) {} }; double cross(Point p0, Point p1, Point p2) { return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y); } //排序方法不一样 bool cmp(Point a, Point b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y; // y从小到大和从大到小都行 } double dis(Point a, Point b) { return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y)); } Point list[maxn], stk[maxn]; int n, p; double ans; void andrew() { p = 1; stk[0] = list[0], stk[1] = list[1]; for (int i = 2; i < n; ++i) { //求下凸包 while (p > 0 && cross(stk[p - 1], stk[p], list[i]) <= 0) --p; stk[++p] = list[i]; } stk[++p] = list[n - 2]; for (int i = n - 3; i >= 0; --i) { //求上凸包 while (p > 0 && cross(stk[p - 1], stk[p], list[i]) <= 0) --p; stk[++p] = list[i]; } //要注意栈尾和栈顶都是list[0] } int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%lf%lf", &list[i].x, &list[i].y); sort(list, list + n, cmp); andrew(); for (int i = 0; i < p; ++i) ans += dis(stk[i], stk[i + 1]); printf("%.2f\n", ans); return 0; }