描述
在一个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
因为有两个断点需要枚举
所以单纯的三分是没法做到
考虑到如果我们已经固定了一个断点
那就可以三分求出另一个断点的最优值
那我们可以对这个断点三分
然后对于每个三分的值再三分一次
然后......就是九分了
#includeusing namespace std;#define ll long longconst double eps=1e-4;inline int read(){ char ch=getchar(); int res=0; while(!isdigit(ch))ch=getchar(); while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar(); return res;}double ax,ay,bx,by,cx,cy,dx,dy,p,q,r;inline double dis(double x1,double x2,double y1,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}inline double calc(double x1,double x2,double y1,double y2){ return dis(ax,x1,ay,y1)/p+dis(x1,x2,y1,y2)/r+dis(x2,dx,y2,dy)/q;}inline double solve(double x,double y){ double lx=cx,ly=cy,rx=dx,ry=dy; while(fabs(lx-rx)>=eps||fabs(ly-ry)>=eps){ double x1=lx+(rx-lx)/3,x2=lx+(rx-lx)*2/3,y1=ly+(ry-ly)/3,y2=ly+(ry-ly)*2/3; if(calc(x,x1,y,y1)>calc(x,x2,y,y2))lx=x1,ly=y1; else rx=x2,ry=y2; } return calc(x,lx,y,ly);}int main(){ cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy>>p>>q>>r; double lx=ax,ly=ay,rx=bx,ry=by; while(fabs(lx-rx)>=eps||fabs(ly-ry)>=eps){ double x1=lx+(rx-lx)/3,x2=lx+(rx-lx)*2/3,y1=ly+(ry-ly)/3,y2=ly+(ry-ly)*2/3; if(solve(x1,y1)