[FROM WOJ]#1359 传送带

#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;
}
上一篇:算法第二章 实践报告


下一篇:leetCode 4. Median of Two Sorted Arrays