【NOIP2016提高A组模拟8.14】传送带

Description

在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。FTD在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在FTD想从A点走到D点，他想知道最少需要走多长时间

Input

输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By 第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy 第三行是3个整数，分别是P，Q，R

Output

输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位

Sample Input

0 0 0 100 100 0 100 100 2 2 1

Sample Output

136.60

Data Constraint

对于30%的数据 1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=10 1<=P,Q,R<=5 对于100%的数据 1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000 1<=P,Q,R<=10

Solution

又是图

因为它是从A点走到Ｄ点，而Ａ是第一个传送带的起点，Ｄ是第二个传送带的终点，所以它的路径必定是从Ａ出发走传送带到某个点下来，直线走到第二个传送带的某个点然后走到终点 那就枚举两个分界点就行了，不过枚举是肯定不行的，但是有不满足二分，然后发现满足三分 那就三分吧 三分套三分就行了 有些人表示不会三分，其实和二分差不多，只不过是中间变成两个点。 一个是 m=(l+r)/2 另一个是 mm=(m+r)/2 ，判断哪个更接近，改变另一个 这题有个问题：它的线可能平行于x轴或y轴，那就x轴和Y轴分别三分就行了

Code

#include<cstdio> #include<cstring> #include<cmath> #define fo(i,a,b) for(int i=a;i<=b;i++) #define db double #define sqr(x) ((x)*(x)) using namespace std; db ax,ay,bx,by,cx,cy,dx,dy,v1,v2,v3; db jl(db ax,db ay,db bx,db by){return sqrt(sqr(ax-bx)+sqr(ay-by));} db min(db a,db b){return a<b?a:b;} db pd(db x,db y) { db l=cx,r=dx,l1=cy,r1=dy,ks=jl(ax,ay,x,y)/v1; while(abs(r-l)>0.00001||abs(r1-l1)>0.00001) { db m1=(l+r)/2,m2=(m1+r)/2,m3=(l1+r1)/2,m4=(m3+r1)/2; db jl1=ks+jl(x,y,m1,m3)/v3+jl(m1,m3,dx,dy)/v2,jl2=ks+jl(x,y,m2,m4)/v3+jl(m2,m4,dx,dy)/v2; if(jl1<jl2) r=m2,r1=m4;else l=m1,l1=m3; } db jl1=ks+jl(x,y,l,l1)/v3+jl(l,l1,dx,dy)/v2,jl2=ks+jl(x,y,r,r1)/v3+jl(r,r1,dx,dy)/v2; return min(jl1,jl2); } int main() { scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by); scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy); scanf("%lf%lf%lf",&v1,&v2,&v3); db l=ax,r=bx,l1=ay,r1=by; while(abs(r-l)>0.00001||abs(r1-l1)>0.00001) { db m1=(r+l)/2,m2=(m1+r)/2,m3=(r1+l1)/2,m4=(m3+r1)/2; if(pd(m1,m3)<pd(m2,m4)) r=m2,r1=m4;else l=m1,l1=m3; } printf("%.2lf",min(pd(l,l1),pd(r,r1))); }