思路

直徑即最長的兩點的距離
枚舉凸包上的所有邊，對每一條邊找出凸包上離該邊最遠的頂點（用叉積），計算這個頂點到該邊兩個端點的距離，并記錄最大的值。但是注意到當我們逆時針枚舉邊的時候，最遠點的變化也是逆時針的，這樣就可以不用從頭計算最遠點，而可以緊接著上一次的最遠點繼續計算。于是我們得到了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

總結

以上是生活随笔為你收集整理的旋转卡壳求凸包直径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。