#1359 传送带
题面
在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P,在CD上的移动速度为Q,在平面上的移动速度R。现在lxhgww想从A点走到D点,他想知道最少需要走多长时间
输入
输入数据第一行是4个整数,表示A和B的坐标,分别为Ax,Ay,Bx,By
第二行是4个整数,表示C和D的坐标,分别为Cx,Cy,Dx,Dy
第三行是3个整数,分别是P,Q,R
输出
输出数据为一行,表示lxhgww从A点走到D点的最短时间,保留到小数点后2位
样例输入
0 0 0 100
100 0 100 100
2 2 1
样例输出
136.60
数据范围
对于100%的数据,
1<= Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10
SOL
很显然的,答案的路径就是现在 AB 上走,然后走到 CD 的一点,再走完剩下的 一段,于是就可以先三分在 AB 上的转折点,套个三分来三分 CD 上的转折点, 然后直接算就好了。
代码:
#include<bits/stdc++.h>
using namespace std;
#define re register
#define db double
#define il inline
struct node{double x,y;}a[4],v1,v2;
db P,Q,R;
il db mul(db x){return x*x;}
il db dis(db x1,db y1,db x2,db y2){return sqrt(mul(x1-x2)+mul(y1-y2));}
il db getdis(db l1,db l2){
db re x1,x2,y1,y2;
x1=a[0].x+v1.x*l1,y1=a[0].y+v1.y*l1,x2=a[3].x+v2.x*l2,y2=a[3].y+v2.y*l2;
return dis(a[0].x,a[0].y,x1,y1)/P+dis(x1,y1,x2,y2)/R+dis(x2,y2,a[3].x,a[3].y)/Q;
}
il db get(db l1){
db re L=0,R=1,mid1,mid2;
while(fabs(L-R)>1e-6){
mid1=(L+R)/2,mid2=(mid1+R)/2;
db re k1=getdis(l1,mid1);
db re k2=getdis(l1,mid2);
if(k1<k2)R=mid2;else L=mid1;
}return getdis(l1,L);
}
signed main(){
// freopen("transporter.in","r",stdin);
// freopen("transporter.out","w",stdout);
for(int re i=0;i<4;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
scanf("%lf%lf%lf",&P,&Q,&R);
v1.x=a[1].x-a[0].x,v1.y=a[1].y-a[0].y;
v2.x=a[2].x-a[3].x,v2.y=a[2].y-a[3].y;
db re L=0,R=1,mid1,mid2;
while(fabs(R-L)>1e-6){
mid1=(L+R)/2,mid2=(mid1+R)/2;
db re k1=get(mid1);
db re k2=get(mid2);
if(k1<k2)R=mid2;else L=mid1;
}printf("%.2lf",get(L));
return 0;
}