Line belt-白红宇

Line belt

阅读量：7048 次

发布时间：2019-06-28

本文共 2801 字，大约阅读时间需要 9 分钟。

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 

       题意：有两个传送带，由A到B的速度是p，有C到D的速度是q，其他速度是r，求由A到D的最少时间；如图（原创） 

       解题思路：在A，B之间去mid，然后三分求最小时间，三分过程中是A到mid的时间加上mid到D的时间（mid到D的时间，也用三分求，最好写一个函数，求A到mid的时间用三分时，每计算一次，都得在当前状态求一个mid到D的时间），然后就能得出来最小时间； 

       感悟：思路不好想；刚开始想的是，在AB中去mid先求出最合适的mid到D的时间，然后把B转移到mid，然后再在CD上取mid，求最合适的mid；这样不是动态中求得，不行。 

       思路不好写，代码更不好写啊，用do，while能过，用while就过不了； 

       代码： 

       #include 
 #include 
 #include 
 #include 
 #include 
 using namespace std; 
 const double eps=1e-6; 
 struct coordinate 
 { 
     double x; 
     double y; 
 }; 
 coordinate A,B,C,D; 
 int t; 
 double p,q,r; 
 double dis(coordinate a,coordinate b) 
 { 
     double t; 
     t=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 
     //printf("t=%.2f\n",t); 
     return t; 
 }//求两点之间的距离 
 coordinate midc(coordinate a,coordinate b) 
 { 
     coordinate t; 
     t.x=(a.x+b.x)*0.5; 
     t.y=(a.y+b.y)*0.5; 
     return t; 
 }//求坐标的中点 
 double time(coordinate a,coordinate b,coordinate c,coordinate d) 
 { 
     double t; 
     t=dis(a,b)/p+dis(b,c)/r+dis(c,d)/q; 
     //printf("t=%.2f\n",t); 
     return t; 
 }//求路径的总时间 
 double Three_algorithm_1(coordinate a,coordinate c,coordinate d) 
 { 
     double t1,t2; 
     coordinate left,right,mid,midmid; 
     left=c; 
     right=d; 
     do 
     { 
         mid=midc(left,right); 
         midmid=midc(mid,right); 
        // printf("dis(right,left)=%.5f\n",dis(right,left)); 
         t1=dis(a,mid)/r+dis(mid,d)/q; 
         t2=dis(a,midmid)/r+dis(midmid,d)/q; 
         if(t1>t2)left=mid; 
         else right=midmid; 
     }while(dis(right,left)>=eps); 
     return t1; 
 }//先求出A到CD段的最小时间 
 double Three_algorithm_2(coordinate a,coordinate b,coordinate c,coordinate d) 
 { 
     double t1,t2; 
     coordinate left,right,mid,midmid; 
     left=a; 
     right=b; 
     mid=midc(left,right); 
     midmid=midc(mid,right); 
     do 
     { 
         mid=midc(left,right); 
         midmid=midc(mid,right); 
         //printf("dis(right,left)=%.f\n",dis(right,left)); 
         t1=dis(a,mid)/p+Three_algorithm_1(mid,c,d); 
         t2=dis(a,midmid)/p+Three_algorithm_1(midmid,c,d); 
         if(t1>t2)left=mid; 
         else right=midmid; 
     }while(dis(right,left)>=eps); 
     return t1; 
 }//加上前面求出的先求出A到CD段的最小时间，用三分求最少时间 
 int main() 
 { 
     //freopen("in.txt", "r", stdin); 
     scanf("%d",&t); 
     for(int i=0;i 
     { 
         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); 
         printf("%.2lf\n",Three_algorithm_2(A,B,C,D)); 
     } 
 } 