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?
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
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.
time to travel from A to D, round to two decimals.
Sample Input
1
0 0 0
100
100
100 0
100
100
100 2 2
1
1
Sample Output
136.60
题意：有两个传送带，由A到B的速度是p，有C到D的速度是q，其他速度是r，求由A到D的最少时间；如图（原创）
belt" title="Line belt">
解题思路：在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));
}
}
#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));
}
}