POJ 2187 Beauty Contest：凸包旋轉卡殼求最遠點對

題目

給定 n 個點，求凸包上最遠點對距離平方。n ≤ 50000。

算法

1. Andrew 算法 O(n log n) 求凸包（去重、排序、上下凸包合併）。
2. 旋轉卡殼 O(h) (h 為凸包頂點數) 求直徑：雙指針平行移動，計算對踵點對距離。

代碼框架

struct Pt { int x,y; };
Pt operator-(Pt a, Pt b) { return {a.x-b.x, a.y-b.y}; }
ll cross(Pt a, Pt b) { return (ll)a.x*b.y - (ll)a.y*b.x; }
ll dist2(Pt a, Pt b) { ll dx=a.x-b.x, dy=a.y-b.y; return dx*dx+dy*dy; }

vector convex_hull(vector p) {
    sort(p.begin(), p.end(), [](Pt a,Pt b){ return a.x!=b.x?a.x ch;
    for (auto pt: p) {
        while (ch.size()>=2 && cross(ch.back()-ch[ch.size()-2], pt-ch.back()) <= 0) ch.pop_back();
        ch.push_back(pt);
    }
    int k = ch.size();
    for (int i=p.size()-2; i>=0; --i) {
        while (ch.size()>k && cross(ch.back()-ch[ch.size()-2], p[i]-ch.back()) <= 0) ch.pop_back();
        ch.push_back(p[i]);
    }
    if (!ch.empty()) ch.pop_back(); // 首尾重複
    return ch;
}

ll rotating_calipers(vector ch) {
    int n = ch.size(); if (n<=1) return 0;
    ll ans = 0;
    for (int i=0, j=1; i 0) j = (j+1)%n;
        ans = max(ans, dist2(ch[i], ch[j]));
        ans = max(ans, dist2(ch[ni], ch[j]));
    }
    return ans;
}

複雜度

O(n log n) 主要在排序，凸包與卡殼均線性。