The Fourth Dimension Space

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

HDOJ 3400 三分法

1Y。只是不明白为什么可以套两个三分,不过从实际情况来看,在第一条直线上三分应该也是符合凸函数性质的。

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

#define eps 1e-8


struct point
{
    
double x,y;
}
;
point a,b,c,d;
double p,q,r;

double dist(point a,point b)
{
    
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}


double cal(double t1,double t2)//以t1,t2为参数算出时间
{
    point tm1;
    point tm2;
    tm1.x
=a.x+(b.x-a.x)*t1;
    tm1.y
=a.y+(b.y-a.y)*t1;

    tm2.x
=c.x+(d.x-c.x)*t2;
    tm2.y
=c.y+(d.y-c.y)*t2;


    
return dist(tm1,a)/p+dist(tm2,d)/q+dist(tm1,tm2)/r;
}



double sanfen(double t1)//在确定t1的基础上得最小值
{
    
double l=0;
    
double r=1;
    
while(l+eps<=r)
    
{

        
double mid=(l+r)/2;
        
double mmid=(mid+r)/2;
        
if(cal(t1,mid)<cal(t1,mmid))
            r
=mmid;
        
else
            l
=mid;
    }

    
return cal(t1,l);
}




int main()
{
    
int ca;
    scanf(
"%d",&ca);
    
while(ca--)
    
{
        scanf(
"%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
        scanf(
"%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);
        
//
        scanf("%lf%lf%lf",&p,&q,&r);

        
double l,r;
        l
=0;r=1;
        
while(l+eps<=r)
        
{

            
double mid=(l+r)/2;
            
double mmid=(mid+r)/2;
            
if(sanfen(mid)<sanfen(mmid))
                r
=mmid;
            
else
                l
=mid;
        }

        printf(
"%.2lf\n",sanfen(l));
    }


    
return 0;
}

posted on 2010-11-07 20:57 abilitytao 阅读(307) 评论(0)  编辑 收藏 引用


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