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