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)/+(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 阅读(578) 评论(1)  编辑 收藏 引用

评论

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

涛神  回复  更多评论   


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