灯泡

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 979 字

三分人所站位置求地面影长加墙上影高

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1438
// 题意：灯高 H、人高 h、灯到墙距离 D，人从灯底走向墙，求「地面影长 + 墙上投影高度」总长的最大值，保留 3 位小数。
// 思路：三分法求单峰函数的最大值。
// 1. 设人离灯的水平距离为 x，灯的光线经头顶后打在 x = D 处的高度 y = H + (h - H) * D / x。
// 2. y > 0 时光打在墙上，总长 = (D - x) + y；否则光提前落地，总长 = x * h / (H - h)。
// 3. 总长关于 x 是先增后减的单峰函数，三分即可。
// 复杂度：O(log(1/eps)) 时间 / O(1) 空间
// 易错点：x = 0 时公式除零，三分从区间内部取点不会取到 0，但仍要保证 H > h 时 (H - h) 不为 0。
// 易错点：影子长度的公式要分「打到墙上」和「打到地面」两种情况，混用会导致三分结果偏大。
#include <bits/stdc++.h>
using namespace std;
int main(){
    double H, h, D;
    if(!(cin >> H >> h >> D)) return 0;
    auto calc = [&](double x){
        double y = H + (h - H) * D / x;
        if(y > 0) return (D - x) + y;
        return x * h / (H - h);
    };
    double l = 0, r = D;
    for(int it = 0; it < 100; it++){
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if(calc(m1) < calc(m2)) l = m1;
        else r = m2;
    }
    cout << fixed << setprecision(3) << calc((l + r) / 2) << "\n";
    return 0;
}

灯泡

正文

一本通·提高篇的其它内容