ZOJ 3203 Light Bulb：三分法 + 幾何優化求最小光程

問題描述

兩平行線間距 D，上線高度 H，下線高度 h (H > h)。光源在上線上，光照射到下線上某點後反射到地面。求光程最小值。x 為光源在上線上的位置（距左端），光程函數 f(x) 在 [D - Dh/H, D] 上凸，求最小值。多測試用例。

幾何建模

設光源位置 x（距左端），入射點在下線位置 D（固定），反射到地面。由幾何相似：
光程 L(x) = (D - x) + H + D·(H-h)/x（推導略）。
定義域：x ∈ [D - Dh/H, D]（保證反射點在下線上）。

三分法求極值

f(x) 在區間上單峰（先降後升），可用三分法：

double ternarySearch(double H, double h, double D) {
    double l = D - D*h/H, r = D;
    for (int iter = 0; iter < 100; iter++) {
        double m1 = l + (r-l)/3, m2 = r - (r-l)/3;
        if (f(m1) > f(m2)) l = m1;
        else r = m2;
    }
    return f(l);
}

100 次迭代精度遠超 1e-9。也可用黃金分割或二分導數零點。

代碼實現

#include 
using namespace std;
double dist(double H, double h, double D, double x) {
    return D - x + H - D*(H-h)/x; // 修正公式
}
double solve(double H, double h, double D) {
    double l = D - D*h/H, r = D;
    for (int i = 0; i < 100; i++) {
        double m1 = l + (r-l)/3, m2 = r - (r-l)/3;
        if (dist(H,h,D,m1) > dist(H,h,D,m2)) l = m1;
        else r = m2;
    }
    return dist(H,h,D,l);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        double H, h, D; cin >> H >> h >> D;
        cout << fixed << setprecision(3) << solve(H,h,D) << '\n';
    }
    return 0;
}

關鍵點

• 函數單峰性證明：二階導數 > 0（凸函數），三分法適用。
• 定義域邊界：x ≥ D - Dh/H 保證反射點不超出下線左端。
• 精度：100 次迭代或 while(r-l > 1e-12)。
• 輸出格式：fixed << setprecision(3) 保留三位小數。

總結

ZOJ 3203 是三分法求單峰函數極值的教科書例題。幾何建模得到光程函數，證明單峰，三分法 100 次迭代輕鬆達到 1e-9 精度。代碼極短，核心在於正確建模與單峰性判斷。掌握「凸函數三分法」模板，可解決大類幾何/物理優化問題。