HDU 2348 Turn the Corner：三分法求解汽車轉彎幾何極值

問題場景

汽車長 l、寬 w，從寬度為 x 的道路轉入寬度為 y 的垂直道路。判斷汽車能否通過轉彎。輸入多組實數 x, y, l, w，輸出 "yes" 或 "no"。

幾何模型與極值函數

設轉彎過程中汽車與外牆夾角為 θ ∈ (0, π/2)。幾何推導可得汽車對面道路佔用的最大寬度函數：

h(θ) = (l·cosθ + w·sinθ - x)·tanθ + w·cosθ

汽車能通過 ⟺ 存在 θ 使 h(θ) ≤ y。因 h(θ) 在區間上先增後減（凸函數），可用三分法求最小值 h_min，再與 y 比較。

三分法實現

double cal(double a) {
    double s = l*cos(a) + w*sin(a) - x;
    return s*tan(a) + w*cos(a);
}

int main() {
    double x,y,l,w;
    while (scanf("%lf%lf%lf%lf",&x,&y,&l,&w)==4) {
        double L=0, R=M_PI/2;
        for (int iter=0; iter<100; iter++) {
            double lm = (2*L + R)/3;
            double rm = (L + 2*R)/3;
            if (cal(lm) > cal(rm)) R = rm;
            else L = lm;
        }
        puts(cal(L) <= y + 1e-9 ? "yes" : "no");
    }
    return 0;
}

注意事項

• 輸入至 EOF，實數讀取用 %lf。
• 三分迭代 80~100 次足夠雙精度收斂。
• 比較時加小 EPS (1e-9) 避免精度誤判。
• M_PI 需 #define _USE_MATH_DEFINES 或自行定義。

複雜度

每組測試 O(log(精度))，極快。

總結

HDU 2348 將幾何問題轉化為單變量凸函數極值求解，三分法完美契合。關鍵在於正確推導 h(θ) 並識別其單峰性。此類「移動物體通過走廊」問題常見於計算幾何與機器人路徑規劃。