The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

ZOJ 3203 Light Bulb (三分法)

这么简单的东西今天才接触到，原来单调的时候用二分，凸的时候用三分（当然求导也行，只是一般解不出来)，三分可代替二分。

公式:x属于区间[D(H-h)/H,D]
影子长度=return (D*h-D*H+x*H)/x +(D-x);

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

#define eps 1e-9
double D,H,h;


double cal(double x)
{
    return (D*h-D*H+x*H)/x +(D-x);
}

int main()
{
    int ca;
    scanf("%d",&ca);

    while(ca--)
    {

        scanf("%lf%lf%lf",&H,&h,&D);
        double l,r;
        l=D*(H-h)/H;r=D;
        while(fabs(r-l)>=eps)
        {
            double mid=(l+r)/2;
            double mmid=(r+mid)/2;
            if(cal(mid)>cal(mmid))
                r=mmid;
            else
                l=mid;
        }

        printf("%.3lf\n",cal(l));
    }

    return 0;
}

posted on 2010-11-07 18:28 abilitytao 阅读(579) 评论(1)  编辑 收藏 引用

评论

# re: ZOJ 3203 Light Bulb (三分法) 2011-07-08 18:21 lvton

涛神  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理