ZOJ Problem Set - 3203 Light Bulb 【三分法】

浅浅的花香味﹌ 2022-08-13 12:52 64阅读 0赞

题目：[ZOJ Problem Set - 3203 Light Bulb ][ZOJ Problem Set - 3203 Light Bulb]

题意：![showImage.do_name_light_bulb_1037_ddd01.gif][]

如图，有个人在地上走，然后他的影子可以投影到墙上或者地上，问影子最长是多少？

分析：

我们知道，三分法是解决一个凹或凸函数的极大极小值，发现这个影子从刚好投影到右下角开始便是一个凸函数，他的影子长度是先递增后递减的，所以可以用三分法。

三分法的原理：

![1358837849_6118.jpg][]

AC代码：

#include <cstdio>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    #include <map>
    #include <string>
    #include <iostream>
    
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    typedef long long LL;
    double H,h,d;
    double solve(double x)
    {
        return  d - x + H - d*(H-h)/x;  //地上+墙上
    }
    //三分法
    double Yougth(double l,double r)
    {
        while(l+1e-10<r)
        {
            double mid = (l + r)/2;
            double midmid = (mid + r)/2;
            if(solve(mid) - solve(midmid)<0)
                l = mid;
            else
                r = midmid;
        }
        return l;
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%lf%lf%lf",&H,&h,&d);
            double cs = Yougth(d - d*h/H,d);
            printf("%.3lf\n",solve(cs));
        }
        return 0;
    }

[ZOJ Problem Set - 3203 Light Bulb]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3366
[showImage.do_name_light_bulb_1037_ddd01.gif]: /images/20220810/e3691c43cd524c10ad94b29bfa71fccf.png
[1358837849_6118.jpg]: https://img-my.csdn.net/uploads/201301/22/1358837849_6118.jpg