首页 > 代码库 > ZOJ Problem Set - 3203 Light Bulb 【三分法】

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

题目:ZOJ Problem Set - 3203 Light Bulb 


题意:

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


分析:

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

三分法的原理:



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 【三分法】