【题目描述】
在一个 2 维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段 AB 和线段 CD。lxhgww 在 AB上的移动速度为 P ，在 CD 上的移动速度为 Q，在平面上的移动速度 R。现在 lxhgww 想从 A 点走到 D 点，他想知道最少需要走多长时间。
【题目链接】
https://loj.ac/problem/10017
【算法】
猜想两条线段的最优点均满足单峰性质，于是三分套三分，代码借鉴黄学长。（http://hzwer.com/4255.html）
【代码】
1 #include <bits/stdc++.h> 2 #define eps 1e-4 3 using namespace std; 4 int ax,ay,bx,by; 5 int cx,cy,dx,dy; 6 int p,q,r; 7 inline int read() { 8 int x=0,f=1; char c=getchar(); 9 while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();} 10 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 11 return x*f; 12 } 13 double dis(double x1,double y1,double x2,double y2) { 14 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); 15 } 16 double cal(double x,double y) { 17 double lx=cx,ly=cy,rx=dx,ry=dy; 18 double lmx,lmy,rmx,rmy,t1,t2; 19 while(fabs(lx-rx)>eps||fabs(ly-ry)>eps) { 20 lmx=lx+(rx-lx)/3,lmy=ly+(ry-ly)/3; 21 rmx=lx+(rx-lx)/3*2,rmy=ly+(ry-ly)/3*2; 22 t1=dis(x,y,lmx,lmy)/r+dis(lmx,lmy,dx,dy)/q; 23 t2=dis(x,y,rmx,rmy)/r+dis(rmx,rmy,dx,dy)/q; 24 if(t1>t2) lx=lmx,ly=lmy; 25 else rx=rmx,ry=rmy; 26 } 27 return dis(ax,ay,x,y)/p+dis(x,y,lmx,lmy)/r+dis(lmx,lmy,dx,dy)/q; 28 } 29 int main() { 30 ax=read(),ay=read(),bx=read(),by=read(); 31 cx=read(),cy=read(),dx=read(),dy=read(); 32 p=read(),q=read(),r=read(); 33 double lx=ax,ly=ay,rx=bx,ry=by; 34 double lmx,lmy,rmx,rmy,t1,t2; 35 while(fabs(lx-rx)>eps||fabs(ly-ry)>eps) { 36 lmx=lx+(rx-lx)/3,lmy=ly+(ry-ly)/3; 37 rmx=lx+(rx-lx)/3*2,rmy=ly+(ry-ly)/3*2; 38 t1=cal(lmx,lmy),t2=cal(rmx,rmy); 39 if(t1>t2) lx=lmx,ly=lmy; 40 else rx=rmx,ry=rmy; 41 } 42 printf("%.2f ",cal(lx,ly)); 43 return 0; 44 }