BZOJ 2458: 最小三角形 - 分治算法優化枚舉

問題描述

給定平面上 N 個點，求由這些點組成的三角形的最小周長。

分治策略

參考最近點對分治思想：按 x 排序，遞歸處理左右半部，獲得當前最優周長 ans。合併階段：只考慮距離中線 ans/2 內的點。將這些點按 y 排序，對左側每個點，只需檢查右側 y 差不超過 ans/2 的點對。經證明，需檢查的點對數量為常數級，總複雜度 O(N log² N) 或優化至 O(N log N)。

關鍵優化

• 遞歸終止閾值設為 20 以下直接暴力枚舉。
• 合併時雙指針維護 y 範圍窗口，避免 O(k²) 暴力。
• 使用 long double 提高精度。

代碼框架

struct Point { double x, y; };
double dist(Point a, Point b) { return hypot(a.x-b.x, a.y-b.y); }

double ans = 1e18;
void solve(int l, int r) {
    if (r - l <= 20) { brute force; return; }
    int mid = (l+r)/2;
    solve(l, mid); solve(mid+1, r);
    double midX = (p[mid].x + p[mid+1].x) / 2;
    // 收集帶內點，按 y 排序，雙指針枚舉更新 ans
}