POJ 2187 Beauty Contest 解題：旋轉卡殼法求凸包直徑平方

題目大意

給定平面上 N 個點，求凸包上最遠點對的距離平方。

演算法步驟

1. 求凸包：Andrew 算法 (單調鏈) O(N log N)，得到逆時針頂點序列 ch[0..m-1]。
2. 旋轉卡殼：對凸包上任意點對，最遠距離必出現在對踵點對。雙指針 u, v，u 遍歷每條邊，v 移動使三角形面積 (叉積) 最大化。

   
   int diameter2(vector& p) {
       vector ch = convexHull(p);
       int n = ch.size();
       if (n <= 1) return 0;
       if (n == 2) return dist2(ch[0], ch[1]);
       ch.push_back(ch[0]); // 方便取模
       int ans = 0;
       for (int u=0, v=1; u

struct Point { int x, y; };
Point operator-(Point a, Point b) { return {a.x-b.x, a.y-b.y}; }
long long cross(Point a, Point b) { return 1LL*a.x*b.y - 1LL*a.y*b.x; }
long long dist2(Point a, Point b) { 
    long long dx=a.x-b.x, dy=a.y-b.y; 
    return dx*dx + dy*dy; 
}