HDU 3400(計算ジオメトリでの三分法利用)
2317 ワード
テーマ:Line belt
标题:あなたに2本の線分AB,CDをあげて、一人でABの上でスピードpを走って、CDの上でqを走って、その他の地方でスピードrを走ります.AからDまでの最低時間はたくさんあります.
标题:あなたに2本の線分AB,CDをあげて、一人でABの上でスピードpを走って、CDの上でqを走って、その他の地方でスピードrを走ります.AからDまでの最低時間はたくさんあります.
#include<iostream>
#include<cmath>
#include <stdio.h>
using namespace std;
typedef struct
{
double x , y ;
}point;
point a,b,c,d;
int p , q , r ;
const double eps = 1e-8;
double dis( point p1 , point p2 )
{
double l = (p2.x-p1.x ) * ( p2.x - p1.x ) + (p2.y-p1.y) * (p2.y - p1.y );
return sqrt(l) ;
}
double part(double k)
{
double Lx = 0 , Rx = dis(c, d);
point e , f1 ,f2;
for(int i = 0 ; i < 200 ;++i)
{
double len = Rx - Lx ;
double t1 = Lx + len * 4/9;
double t2 = Lx + len *5/9;
e.x = a.x + k * (b.x - a.x );
e.y = a.y + k * ( b.y -a.y );
f1.x = c.x + (t1 * (d.x - c.x ));
f1.y = c.y + (t1* (d.y - c.y ));
f2.x = c.x + (t2 * (d.x - c.x ));
f2.y = c.y + (t2 * (d.y - c.y ));
double res1 = dis(a,e)/p + dis(e,f1)/r + dis(f1,d)/q;
double res2 = dis(a,e)/p + dis(e,f2)/r + dis(f2,d)/q;
if( res1 < res2) Rx = t2 ;
else Lx = t1 ;
}
double t = (Lx+Rx)/2.0;
e.x = a.x + (k * (b.x - a.x )) ;
e.y = a.y + (k * ( b.y -a.y )) ;
f1.x = c.x + (t * (d.x - c.x ));
f1.y = c.y + (t* (d.y - c.y));
return dis(a,e)/p + dis(e,f1)/r + dis(f1,d)/q;
}
double solve(double Min , double Max )
{
double Lx = Min , Rx = Max ;
for(int i = 0 ; i < 200 ; ++i)
{
double len = Rx - Lx ;
double t1 = Lx + len * 4/9 ;
double t2 = Lx + len* 5/9 ;
double f1 = part(t1);
double f2 = part(t2);
if( f1 < f2) Rx = t2 ;
else Lx = t1;
}
return part((Lx+Rx)/2.0);
}
int main()
{
int t ;
scanf("%d",&t);
while(t--)
{
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("%d%d%d",&p,&q,&r);
double res = solve(0.0, 1.0);
printf("%.2f
",res);
}
return 0 ;
}