Codeforces 8D Two Friends：三分+二分+計算幾何綜合解法

題目大意

三點：Cinema (C)、House (H)、Shop (S)。Alan 從 H 經 S 回 C，Bob 從 H 直接回 C。兩人可共同行走一段路徑。給定 Alan 繞路容限 t1，Bob 繞路容限 t2，求**最大共同路徑長度**。

幾何建模

• 共同路徑 = H 到某點 X 的線段
• X 在線段 HS 上 (參數 du ∈ [0,1])
• 分離後：Alan 走 X→S→C，Bob 走 X→C
• 約束：
  |XC| + |XH| ≤ |HC| + t2 (Bob)
  |XC| + |XS| ≤ |SC| + t1 (Alan)

解法：三分套二分

1. 外層三分：在 HS 線段上三分搜索最優分離點 X (單峰函數)
2. 內層二分：固定 X，在 XC 線段上二分搜索最遠共同點 Y (滿足雙方約束)

核心代碼實現

#include <bits/stdc++.h>
using namespace std;

struct Pt { double x, y; };
double t1, t2;
Pt C, H, S;

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

// 固定 X 在 HS 上的位置 (du ∈ [0,1])，求最大共同長度
double work(double du) {
    Pt X = { S.x*(1-du) + H.x*du, S.y*(1-du) + H.y*du };
    double XC = dist(X, C), XS = dist(X, S), XH = dist(X, H);
    
    // 直接分離在 X 處
    if (XC + XH <= dist(H,C) + t2 && XC + XS <= dist(S,C) + t1)
        return min(dist(H,C) + t2 - XH, dist(S,C) + t1 - XS);
    
    // 二分搜索 XC 上的分離點 Y
    double l = 0, r = 1;
    for (int i = 0; i < 100; ++i) {
        double mid = (l + r) / 2;
        Pt Y = { C.x*(1-mid) + X.x*mid, C.y*(1-mid) + X.y*mid };
        double YC = dist(Y, C), YH = dist(Y, H), YS = dist(Y, S);
        if (YC + YH <= dist(H,C) + t2 && YC + YS <= dist(S,C) + t1)
            l = mid;
        else
            r = mid;
    }
    Pt Y = { C.x*(1-l) + X.x*l, C.y*(1-l) + X.y*l };
    return dist(Y, C);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    while (cin >> t1 >> t2) {
        cin >> C.x >> C.y >> H.x >> H.y >> S.x >> S.y;
        
        double HC = dist(H, C), SC = dist(S, C), HS = dist(H, S);
        
        // 特判：Bob 容限足夠繞經 Shop
        if (HC + t2 >= SC + HS) {
            cout << fixed << setprecision(8) << min(SC + t1 + HS, HC + t2) << "\n";
            continue;
        }
        
        t1 += SC + 1e-9; // Alan 總預算：SC + t1
        t2 += HC + 1e-9; // Bob 總預算：HC + t2
        
        // 三分搜索 HS 上的最優分離點
        double l = 0, r = 1, ans = 0;
        for (int i = 0; i < 100; ++i) {
            double m1 = l + (r - l) / 3;
            double m2 = r - (r - l) / 3;
            double f1 = work(m1), f2 = work(m2);
            if (f1 < f2) l = m1;
            else r = m2;
        }
        ans = work((l + r) / 2);
        cout << fixed << setprecision(8) << ans << "\n";
    }
    return 0;
}

關鍵技術點

1. 凸性/單峰性證明

共同路徑長度作為分離點位置的函數是單峰的：

• 分離點過早 → 共同路徑短
• 分離點過晚 → 違反容限約束
• 中間存在唯一最優點 → 三分法適用

2. 參數化線段插值