旋转卡壳求凸包直径

思路

直径即最长的两点的距离
枚举凸包上的所有边，对每一条边找出凸包上离该边最远的顶点（用叉积），计算这个顶点到该边两个端点的距离，并记录最大的值。但是注意到当我们逆时针枚举边的时候，最远点的变化也是逆时针的，这样就可以不用从头计算最远点，而可以紧接着上一次的最远点继续计算。于是我们得到了O(n)的算法。

复制的图

---

常数巨大的丑陋代码

# include <stdio.h> # include <stdlib.h> # include <iostream> # include <string.h> # include <math.h> # include <algorithm> # define RG register # define IL inline # define ll long long # define mem(a, b) memset(a, b, sizeof(a)) # define Min(a, b) (((a) > (b)) ? (b) : (a)) # define Max(a, b) (((a) < (b)) ? (b) : (a)) # define Sqr(a) ((a) * (a)) using namespace std;const int MAXN = 50001; int n, top = 2; struct Point{int x, y, len; } p[MAXN], Point_A, s[MAXN]; //最左下的点 //求叉积(向量ab，向量ac) IL int Cross(Point a, Point b, Point c){return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } //极角排序 IL int Dis(Point a, Point b){return Sqr(a.x - b.x) + Sqr(a.y - b.y); }IL bool Cmp(Point a, Point b){RG int x = Cross(Point_A, a, b);if(x > 0) return 1;else if(x < 0) return 0;a.len = Dis(Point_A, a);b.len = Dis(Point_A, b);return a.len < b.len; }IL void Find(){Point_A = p[1]; RG int temp = 0;for(RG int i = 2; i <= n; i++)if((Point_A.y == p[i].y && Point_A.x > p[i].x) || Point_A.y > p[i].y)Point_A = p[i], temp = i;p[temp] = p[1]; p[1] = Point_A; }IL void Graham(){Find();sort(p + 2, p + n + 1, Cmp);p[++n] = s[0] = p[1]; s[1] = p[2]; s[2] = p[3];for(RG int i = 4; i < n; i++){while(Cross(s[top - 1], s[top], p[i]) <= 0 && top) top--;s[++top] = p[i];}s[++top] = p[n]; }IL int Rot_Cover(){RG int q = 1, ans = 0;for(RG int i = 0; i < top; i++){while(Cross(s[i], s[i + 1], s[q]) < Cross(s[i], s[i + 1], s[q + 1])) q = (q + 1) % top;//等底的情况下,叉积越大即面积越大离该点越远 ans = Max(ans, Dis(s[i], s[q]));ans = Max(ans, Dis(s[i + 1], s[q]));//判断边平行的情况 }return ans; }int main(){scanf("%d", &n);for(RG int i = 1; i <= n; i++)scanf("%d%d", &p[i].x, &p[i].y);if(n == 2) return !printf("%d\n", Dis(p[1], p[2]));Graham();printf("%d\n", Rot_Cover());return 0; }

裸题 Beauty Contest POJ - 2187

转载于:https://www.cnblogs.com/cjoieryl/p/8206403.html

总结

以上是生活随笔为你收集整理的旋转卡壳求凸包直径的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。