HDU 1007 Quoit Design：分治法求最近點對距離

問題描述

給定 N (≤ 100,000) 個平面點，找到最近點對距離，保留兩位小數。多測試用例，N=0 結束。若有重合點，距離為 0。

分治算法核心流程

1. 排序：預先按 x 坐標排序，遞歸過程中按 y 排序合併
2. 分治遞歸：分左右兩半，遞歸求左半、右半最小距離 d
3. 合併檢查橫跨區域：只需檢查 x 距離中線 ≤ d 的點，按 y 排序後，每點只需檢查後續最多 6-7 個點

關鍵幾何結論

在 d×2d 的矩形區域內，若點對距離 ≥ d，最多容納 8 個點（4×2 網格）。故按 y 序掃描時，每點只需與後 7 個點計算距離。

完整 AC 代碼（優化版）

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
struct Point { double x, y; } p[MAXN], tmp[MAXN];

bool cmpX(const Point& a, const Point& b) { return a.x < b.x; }
bool cmpY(const Point& a, const Point& b) { return a.y < b.y; }

double dist(const Point& a, const Point& b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
}

double closest(int l, int r) {
    if (l >= r) return 1e20;
    if (l + 1 == r) return dist(p[l], p[r]);
    
    int mid = (l + r) >> 1;
    double midX = p[mid].x;
    double d = min(closest(l, mid), closest(mid+1, r));
    
    // 合併按 y 排序
    merge(p+l, p+mid+1, p+mid+1, p+r+1, tmp, cmpY);
    copy(tmp, tmp + (r-l+1), p+l);
    
    // 檢查橫跨中線的點
    int cnt = 0;
    static Point strip[MAXN];
    for (int i = l; i <= r; ++i)
        if (fabs(p[i].x - midX) < d)
            strip[cnt++] = p[i];
    
    for (int i = 0; i < cnt; ++i)
        for (int j = i+1; j < cnt && strip[j].y - strip[i].y < d; ++j)
            d = min(d, dist(strip[i], strip[j]));
    
    return d;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; ++i)
            scanf("%lf%lf", &p[i].x, &p[i].y);
        sort(p, p+n, cmpX);
        double ans = closest(0, n-1);
        printf("%.2f\n", ans);
    }
    return 0;
}

優化要點

1. 歸併排序：遞歸返回時用 `merge` 維護 y 序，避免重複排序 O(n log² n) → O(n log n)
2. 靜態臨時數組：避免遞歸中重複分配內存
3. 剪枝條件：`strip[j].y - strip[i].y < d` 提前終止內層循環
4. 邊界處理：`l >= r` 返回無窮大，`l+1==r` 直接計算

複雜度

• 時間：O(n log n)
• 空間：O(n)

常見錯誤

• 忘記 `fabs(p[i].x - midX) < d` 取絕對值
• 合併時範圍寫錯（指針算術）
• 輸出格式：`%.2f` 自動四捨五入