首页 > 代码库 > 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 }
hdu 3400 Line belt
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。