平面最近點對問題：分治算法 O(n log n) 完整解析

問題描述

給定平面 n 個點，求最近點對的歐幾里得距離。

暴力法

O(n²) 枚舉所有點對，n≤10⁴ 可接受，更大需優化。

分治法

1. 按 x 排序，中線 x = mid 分為左右子集。
2. 遞歸求左/右最近距離 d1, d2，d = min(d1,d2)。
3. 合併：只需考慮跨中線且 x 距離 ≤ d 的點。證明：中線左右各以 d 為半徑的正方形最多各容納 6 個點（間距 ≥ d），故對左側帶內每點，只需檢查右側帶內 y 距離 ≤ d 的至多 6 點。
4. 將帶內點按 y 排序，雙指針掃描，時間 O(n)。

複雜度

T(n) = 2T(n/2) + O(n) = O(n log n)。

代碼框架

struct Point { double x, y; };
double dist(Point a, Point b) { return hypot(a.x-b.x, a.y-b.y); }
double closest(vector& pts) {
    sort(pts.begin(), pts.end(), [](auto& a, auto& b){ return a.x < b.x; });
    vector aux(pts.size());
    return cdq(pts, aux, 0, pts.size()-1);
}
double cdq(vector& p, vector& tmp, int l, int r) {
    if (l >= r) return 1e100;
    int mid = (l+r)/2;
    double d = min(cdq(p,tmp,l,mid), cdq(p,tmp,mid+1,r));
    // merge by y
    merge(p.begin()+l, p.begin()+mid+1, p.begin()+mid+1, p.begin()+r+1, tmp.begin(),
          [](auto& a, auto& b){ return a.y < b.y; });
    copy(tmp.begin(), tmp.begin()+(r-l+1), p.begin()+l);
    // strip
    vector strip;
    for (int i=l; i<=r; ++i) if (fabs(p[i].x - p[mid].x) < d) strip.push_back(p[i]);
    for (int i=0; i