ZOJ 2107 / HDU 1007 Quoit Design：分治法求平面最近點對

問題描述

給定平面上 N (≤10⁵) 個點，求最近點對距離除以 2（即最大不重疊圓半徑）。經典最近點對問題。

分治算法 O(N log N)

1. 按 x 排序。
2. 遞歸求左半部、右半部最近距離 d = min(d_L, d_R)。
3. 合併：收集中線左右距離 d 內的點，按 y 排序。對每個點，只需檢查其後 y 差 < d 的最多 6~7 個點（幾何證明）。更新 d。
4. 歸併排序保持 y 有序，避免重複排序。

關鍵優化

• 全局按 x 排序一次，遞歸時用臨時數組按 y 歸併（O(N)）。
• 距離平方比較避免開根號，最後才開根號。
• 合併階段只檢查 y 差 < d 的點，利用幾何性質常數極小。

代碼框架

struct Point { double x, y; };
bool cmpX(Point a, Point b) { return a.x < b.x; }
bool cmpY(Point a, Point b) { return a.y < b.y; }
double dist2(Point a, Point b) { ... }

double solve(Point p[], int l, int r) {
    if (r - l + 1 <= 3) { // brute force
        double d = INF;
        for (int i=l;i<=r;++i)
            for (int j=i+1;j<=r;++j)
                d = min(d, dist2(p[i], p[j]));
        sort(p+l, p+r+1, cmpY);
        return sqrt(d);
    }
    int mid = (l+r)/2;
    double midX = p[mid].x;
    double d = min(solve(p, l, mid), solve(p, mid+1, r));
    // merge by y
    static Point tmp[MAXN];
    int cnt = 0;
    for (int i=l;i<=r;++i)
        if (fabs(p[i].x - midX) < d)
            tmp[cnt++] = p[i];
    // check strip
    for (int i=0;i