ZOJ - 3203 Light Bulb(三分)

题意：灯离地面的高度为$H$，人的身高为$h$，灯离墙的距离为$D$，人站在不同位置，影子的长度不一样，求出影子的最长长度。

思路：设人离灯的距离为$x$，当人走到距离灯长度为$L$时，人在墙上的影子消失，此时人再往前走，影子的长度必然会减小，此时的$L$就为三分的左边界，右边界为$R=D$，由形似三角形可以推导出$L=D-\frac{h*D}{H}$，影子的长度

$$f(x)=D-x+H-\frac{(H-h)*D}{x},x\in [D-\frac{h*D}{H},D]$$

在区间$[D-\frac{h*D}{H},D]$三分求极值即可。

#include <iostream>

#include <algorithm>

#include <cstdio>

using namespace std;

const double eps = 1e-;

int t;

double H, h, D;

double f(double x)

{

    return D - x + H - (H - h) * D / x;

}

double three_devide(double l, double r)

{

    while (r - l > eps) {

        double lmid = (l + r) / ;

        double rmid = (lmid + r) / ;

        if (f(lmid) < f(rmid)) l = lmid;

        else r = rmid;

    }

    return l;

}

int main()

{

    scanf("%d", &t);

    while (t--) {

        scanf("%lf%lf%lf", &H, &h, &D);

        double res = f(three_devide(D - h * D / H, D));

        printf("%.3lf\n", res);

    }

    return ;

}

记录一下三分的模板：

求单峰函数的极值时，如果$f(lmid)<f(rmid)$，则令$l=lmid$，否则令$r=rmid$

求单谷函数的极值时，如果$f(lmid)>f(rmid)$，则令$l=lmid$，否则令$r=rmid$

巴特西

ZOJ - 3203 Light Bulb(三分)

最新文章

热门文章