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

Problem

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

输出数据为一行，表示FTD从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

解题方法：三分（属于分治算法中的一种） 在线段AB上三分分出一个转折点，然后线段CD上套一个三分分出一个转折点，计算距离就OK了。 具体方法：取l,r的两个三分点，然后比哪个三分点更优，如果左边的优就将左指针向右移，否则将右指针向左移。

Code

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #define sp 0.001 using namespace std; double ax,ay,bx,by,cx,cy,dx,dy,da,db,s1,s2,s3,ans,xi,yi,xa,ya,xb,yb; double l1,l2,r1,r2,mid1,mid2,mmid1,mmid2,l3,l4,r3,r4,mid3,mid4,mmid3,mmid4,ans1,ans2; int i,j,n,m; double dis(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } int main() { freopen("4692_7.in","r",stdin); ans=2147483647; scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by); scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy); scanf("%lf%lf%lf",&s1,&s2,&s3); l1=ax;r1=bx; l2=ay;r2=by; while (abs(l1-r1)>=sp || abs(l2-r2)>=sp) { mid1=l1+(r1-l1)/3; mid2=l2+(r2-l2)/3; mmid1=r1-(r1-l1)/3; mmid2=r2-(r2-l2)/3; l3=cx;r3=dx; l4=cy;r4=dy; ans1=2147483647; while (abs(l3-r3)>=sp || abs(l4-r4)>=sp) { mid3=l3+(r3-l3)/3; mid4=l4+(r4-l4)/3; mmid3=r3-(r3-l3)/3; mmid4=r4-(r4-l4)/3; da=dis(ax,ay,mid1,mid2)/s1+dis(mid1,mid2,mid3,mid4)/s3+dis(mid3,mid4,dx,dy)/s2; db=dis(ax,ay,mid1,mid2)/s1+dis(mid1,mid2,mmid3,mmid4)/s3+dis(mmid3,mmid4,dx,dy)/s2; if (da<db) { r3=mmid3; r4=mmid4; ans1=min(ans1,da); } else { l3=mid3; l4=mid4; ans1=min(ans1,db); } } l3=cx;r3=dx; l4=cy;r4=dy; ans2=2147483647; while (abs(l3-r3)>=sp || abs(l4-r4)>=sp) { mid3=l3+(r3-l3)/3; mid4=l4+(r4-l4)/3; mmid3=r3-(r3-l3)/3; mmid4=r4-(r4-l4)/3; da=dis(ax,ay,mmid1,mmid2)/s1+dis(mmid1,mmid2,mid3,mid4)/s3+dis(mid3,mid4,dx,dy)/s2; db=dis(ax,ay,mmid1,mmid2)/s1+dis(mmid1,mmid2,mmid3,mmid4)/s3+dis(mmid3,mmid4,dx,dy)/s2; if (da<db) { r3=mmid3; r4=mmid4; ans2=min(ans2,da); } else { l3=mid3; l4=mid4; ans2=min(ans2,db); } } if (ans1<ans2) { r1=mmid1; r2=mmid2; ans=min(ans,ans1); } else { l1=mid1; l2=mid2; ans=min(ans,ans2); } } printf("%.2lf",ans); }

——2016.8.14