在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。FTD在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在FTD想从A点走到D点，他想知道最少需要走多长时间。
这题我们先假设在AB线段确定了一个点 (x,y) ，那么 (x,y) 到CD线段的一个点 (x′,y′) 的距离加上 (x′,y′) 到D点的时间显然是呈一个二次函数。于是我们可以在AB线段上枚举一个点，三分CD上的点，然后取最优即可。
但是，这样可能会超时，我们考虑点A到 (x,y) 的时间随着距离增大而增大，这说明这里的函数是一条直线，那么显然 (x,y) 也可以三分出来。这样时间复杂度是 O(log23L) （ L <script type="math/tex" id="MathJax-Element-8">L</script>是线段最长距离），所以是很快的。
请自重！
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) #define eps 0.001 using namespace std; double sqr(double x) {return x*x;} double dis(double x,double y,double x1,double y1) { return sqrt(sqr(x-x1)+sqr(y-y1)); } double calc(double z1,double z2,double z3) {return z1*z3/z2;} double ax,ay,bx,by; double cx,cy,dx,dy; int P,Q,R; double ab,cd; double val(double x,double y,double x1,double y1) { return dis(ax,ay,x,y)/P+dis(x,y,x1,y1)/R+dis(dx,dy,x1,y1)/Q; } double sf(double x,double y) { double l=0,r=dis(cx,cy,dx,dy); double tmp=2147483647; while(l+eps<r) { double p; double lm=l+(r-l)/3; double rm=r-(r-l)/3; double lx,ly; p=calc(lm,cd,fabs(dx-cx)); if(dx<cx) lx=cx-p; else lx=cx+p; p=calc(lm,cd,fabs(dy-cy)); if(dy<cy) ly=cy-p; else ly=cy+p; double rx,ry; p=calc(rm,cd,fabs(dx-cx)); if(dx<cx) rx=cx-p; else rx=cx+p; p=calc(rm,cd,fabs(dy-cy)); if(dy<cy) ry=cy-p; else ry=cy+p; if(val(x,y,lx,ly)<val(x,y,rx,ry)) r=rm,tmp=val(x,y,lx,ly); else l=lm,tmp=val(x,y,rx,ry); } return tmp; } int main() { cin>>ax>>ay>>bx>>by; ab=dis(ax,ay,bx,by); cin>>cx>>cy>>dx>>dy; cd=dis(cx,cy,dx,dy); cin>>P>>Q>>R; double ans=2147483647; double l=0,r=ab; if(ax==bx && ay==by) ans=sf(ax,ay); while(l+eps<r) { double lm=l+(r-l)/3; double rm=r-(r-l)/3; double lx,ly; double p=calc(lm,ab,fabs(bx-ax)); if(bx<ax) lx=ax-p; else lx=ax+p; p=calc(lm,ab,fabs(by-ay)); if(by<ay) ly=ay-p; else ly=ay+p; double rx,ry; p=calc(rm,ab,fabs(bx-ax)); if(bx<ax) rx=ax-p; else rx=ax+p; p=calc(rm,ab,fabs(by-ay)); if(by<ay) ry=ay-p; else ry=ay+p; double t1=sf(lx,ly),t2=sf(rx,ry); if(t1<t2) ans=t1,r=rm; else ans=t2,l=lm; } printf("%.2lf",ans); }