HDU 4717 The Moving Points：三分法求動態點集的最小最大距離

題目背景

給定 n 個移動點，每個點擁有初始座標 (x, y) 以及單位時間內的位移向量 (vx, vy)。隨著時間 t 流逝，所有點的位置會發生線性變化。我們需要找出某一時刻 t，使得該時刻任意兩點之間的最大歐氏距離達到最小值，並輸出該最小最大距離與對應的時間。

核心觀察：單峰函數與三分法

將「時間 t」與「所有點對中的最大距離 d(t)」建立函數關係。由於每個點的軌跡為直線，兩點距離的平方為關於 t 的二次函數，其上包絡線（即最大距離）呈現「先遞減後遞增」的單峰特性。因此，我們可以直接對時間軸施行三分法，快速逼近極值點。

算法流程

1. 初始化搜索區間 [L, R]，其中 L = 0，R 取一個足夠大的常數（如 1e6）。
2. 重複以下步驟直到區間長度小於 eps（如 1e-6）：
   • 將區間三等分，得到 midL = L + (R-L)/3、midR = R - (R-L)/3。
   • 計算 f(midL) 與 f(midR)，其中 f(t) 為時刻 t 下的最大點對距離。
   • 若 f(midL) < f(midR)，說明極值在左側，令 R = midR；否則令 L = midL。
3. 最終取 t = L，輸出 t 與 f(t)，保留兩位小數。

關鍵函數實現

double maxDist(double t) {
    double ans = 0;
    for (int i = 0; i < n; ++i) {
        double xi = s[i].x + p[i].x * t;
        double yi = s[i].y + p[i].y * t;
        for (int j = i + 1; j < n; ++j) {
            double xj = s[j].x + p[j].x * t;
            double yj = s[j].y + p[j].y * t;
            ans = max(ans, hypot(xi - xj, yi - yj));
        }
    }
    return ans;
}

複雜度分析

每次評估 f(t) 需 O(n^2)，三分法迭代次數約 log_{1.5}(R/eps)，總體複雜度 O(n^2 log R)，對於 n ≤ 300 完全足夠。

總結

本題展示了如何將動態幾何問題轉化為單變量單峰函數優化，三分法以其簡潔易實現的特點，成為解決此類「最小化最大值」問題的利器。