NYOJ 253 LK的旅行：旋轉卡殼法求凸包直徑（最遠點對距離平方）

題目大意

給定平面上 m (3 ≤ m ≤ 100,000) 個點（坐標 0~10000，可能重複），求最遠點對的距離平方。多組測試數據。

核心算法：旋轉卡殼

幾何結論：最遠點對必定在凸包上。步驟：

1. 求點集的凸包（Andrew 算法 / 單調鏈，O(m log m)）
2. 在凸包上應用旋轉卡殼找最遠點對（O(h)，h 為凸包點數）

關鍵代碼實現

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define NN 100005

struct Point { int x, y; } a[NN], q[NN];
int top;

// 距離平方
int dis2(Point p1, Point p2) {
    return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}

// 叉積：(p1-p) × (p2-p)
int cross(Point p, Point p1, Point p2) {
    return (p1.x-p.x)*(p2.y-p.y) - (p1.y-p.y)*(p2.x-p.x);
}

// 排序：先 x 後 y
int cmp(const void *x, const void *y) {
    Point *p1 = (Point*)x, *p2 = (Point*)y;
    if (p1->x != p2->x) return p1->x - p2->x;
    return p1->y - p2->y;
}

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d%d", &a[i].x, &a[i].y);
        
        qsort(a, n, sizeof(Point), cmp);
        
        // Andrew 算法求凸包（去重）
        top = 0; q[0] = a[0];
        for (int i = 1; i < n; ++i) {  // 下凸包
            if (a[i].x == q[top].x && a[i].y == q[top].y) continue;
            while (top >= 1 && cross(q[top-1], q[top], a[i]) >= 0) --top;
            q[++top] = a[i];
        }
        int t = top;
        for (int i = n-1; i >= 0; --i) {  // 上凸包
            if (a[i].x == q[top].x && a[i].y == q[top].y) continue;
            while (top > t && cross(q[top-1], q[top], a[i]) >= 0) --top;
            q[++top] = a[i];
        }
        
        // 旋轉卡殼求直徑
        double ans = 0;
        t = 1;
        for (int i = 0; i < top; ++i) {
            // 移動 t 直到三角形面積不再增大
            while (cross(q[i+1], q[t], q[i]) > cross(q[i+1], q[t+1], q[i]))
                t = (t + 1) % top;
            ans = fmax(ans, fmax(dis2(q[i], q[t]), dis2(q[i+1], q[t+1])));
        }
        
        printf("%.0lf\n", ans);
    }
    return 0;
}

算法細節解析

1. 凸包構建 (Andrew 算法)

• 按 x 升序、y 升序排序
• 構建下凸包：維持左轉（叉積 > 0），右轉或共線則彈棧
• 構建上凸包：逆序遍歷，同理維持左轉
• 去重：跳過與棧頂坐標相同的點

2. 旋轉卡殼核心邏輯

• 對凸包上每條邊 q[i] → q[i+1]，找到距離最遠的對踵點 q[t]
• 判斷條件：cross(q[i+1], q[t], q[i]) > cross(q[i+1], q[t+1], q[i])
  即：三角形 (q[i], q[i+1], q[t+1]) 面積 > (q[i], q[i+1], q[t]) 面積
• t 只單向遞增（模 top），總體 O(h)
• 候選最遠對：(q[i], q[t]) 和 (q[i+1], q[t+1])

複雜度

• 排序：O(m log m)
• 凸包：O(m)
• 旋轉卡殼：O(h) ≤ O(m)
• 總體：O(m log m)，滿足 m ≤ 100,000

前置知識鏈接

建議先完成 NYOJ 78 圈水池（凸包周長），本題為其變體：求凸包直徑而非周長。