分類  >  編程 >

HDU 3400 Line belt 3分

tags:    時間:2014-05-04 18:39:43
HDU 3400 Line belt 三分
點擊打開鏈接

Line belt

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2615    Accepted Submission(s): 990


Problem Description
In a two-dimensional plane there are two line belts, there are two segments AB and CD, lxhgww's speed on AB is P and on CD is Q, he can move with the speed R on other area on the plane.
How long must he take to travel from A to D?
 

Input
The first line is the case number T.
For each case, there are three lines.
The first line, four integers, the coordinates of A and B: Ax Ay Bx By.
The second line , four integers, the coordinates of C and D:Cx Cy Dx Dy.
The third line, three integers, P Q R.
0<= Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10
 

Output
The minimum time to travel from A to D, round to two decimals.
 

Sample Input
1 0 0 0 100 100 0 100 100 2 2 1
 

Sample Output
136.60
 

Author
lxhgww&&momodi

在二維平面上,有兩條線段分別是AB和CD,傳送帶在AB上的速度是p,在CD上的速度是q,在其餘地方的速度是r,求傳送帶從A點到D點的最快時間是多少。
三分求解。
先三分AB這條線段,然後在此基礎上在三分CD這條線段,最後即可求得最少時間。
//15MS	228K #include<stdio.h> #include<math.h> double p,q,rr; struct Point {     double  x,y; }; double dis(Point A,Point B) {     return sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y)); } double calc(Point x,Point C,Point D) {     Point l=C,r=D,mid,midmid;     double mid_area,midmid_area;     do//三分CD的長度     {         mid.x=(l.x+r.x)/2;mid.y=(l.y+r.y)/2;         midmid.x=(mid.x+r.x)/2;midmid.y=(mid.y+r.y)/2;         mid_area=dis(mid,D)/q+dis(x,mid)/rr;         midmid_area=dis(midmid,D)/q+dis(x,midmid)/rr;         if(mid_area>midmid_area)l=mid;         else r=midmid;     }while(dis(l,r)>=1e-9);     return mid_area; } int main() {     int t;     scanf("%d",&t);     while(t--)     {         Point A,B,C,D;         scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&D.x,&D.y);         scanf("%lf%lf%lf",&p,&q,&rr);         Point l=A,r=B,mid,midmid;         double mid_area,midmid_area;         do//三分AB的長度         {             mid.x=(r.x+l.x)/2;mid.y=(r.y+l.y)/2;             midmid.x=(r.x+mid.x)/2;midmid.y=(r.y+mid.y)/2;             mid_area=dis(A,mid)/p+calc(mid,C,D);             midmid_area=dis(A,midmid)/p+calc(midmid,C,D);             if(mid_area<midmid_area)r=midmid;             else l=mid;         }while(dis(l,r)>=1e-9);         printf("%.2lf\n",mid_area);     }     return 0; } 


推薦閱讀文章

Bookmark the permalink ,來源:互聯網