首页 > 代码库 > hdu 3400 Line belt

hdu 3400 Line belt

题意:给你两条线段AB,CD;然后给你在AB,CD上的速度P,Q,在其它部分的速度是R,然后求A到D的最短时间。

思路:用三分枚举从AB线段上离开的点,然后再用三分枚举在CD的上的点找到最优点,求距离和时间就可以。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 using namespace std; 6 const double eps=1e-8; 7  8 int t; 9 double p,q,r;10 struct point11 {12      double x,y;13 }a,b,c,d;14 15 double sqr(double x)16 {17     return x*x;18 }19 20 double dis(double x1,double y1,double x2,double y2)21 {22     return sqrt(sqr(x1-x2)+sqr(y1-y2)+eps);23 }24 25 double ok(double t1)26 {27     point pos;28     pos.x=a.x+(b.x-a.x)*((t1*p)/dis(a.x,a.y,b.x,b.y));29     pos.y=a.y+(b.y-a.y)*((t1*p)/dis(a.x,a.y,b.x,b.y));30     double l1=0,r1=dis(c.x,c.y,d.x,d.y)/q;31     while(r1-l1>eps)32     {33         double mid1=(r1+l1)/2;34         double mid2=(mid1+r1)/2;35         double x1=d.x+(c.x-d.x)*((mid1*q)/dis(c.x,c.y,d.x,d.y));36         double y1=d.y+(c.y-d.y)*((mid1*q)/dis(c.x,c.y,d.x,d.y));37         double x2=d.x+(c.x-d.x)*((mid2*q)/dis(c.x,c.y,d.x,d.y));38         double y2=d.y+(c.y-d.y)*((mid2*q)/dis(c.x,c.y,d.x,d.y));39         double d1=dis(pos.x,pos.y,x1,y1)/r;40         double d2=dis(pos.x,pos.y,x2,y2)/r;41         if(d1+mid1<=d2+mid2)42         {43             r1=mid2;44         }45         else46             l1=mid1;47     }48     double xx=d.x+(c.x-d.x)*(l1*q)/dis(c.x,c.y,d.x,d.y);49     double yy=d.y+(c.y-d.y)*(l1*q)/dis(c.x,c.y,d.x,d.y);50     return dis(pos.x,pos.y,xx,yy)/r+t1+l1;51 }52 53 int main()54 {55     scanf("%d",&t);56     while(t--)57     {58         scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);59         scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);60         scanf("%lf%lf%lf",&p,&q,&r);61         double ll=0,rr=dis(a.x,a.y,b.x,b.y)/p;62         while(rr-ll>eps)63         {64             double mid1=(ll+rr)/2;65             double mid2=(mid1+ll)/2;66             if(ok(mid2)>=ok(mid1))67             {68                 ll=mid2;69             }70             else71                 rr=mid1;72         }73         printf("%.2lf\n",ok(ll));74     }75 }
View Code

 

hdu 3400 Line belt