【SCOI2010】【JZOJ4692】传送带

本文主要是介绍【SCOI2010】【JZOJ4692】传送带，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。FTD在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在FTD想从A点走到D点，他想知道最少需要走多长时间。

Solution

这题我们先假设在AB线段确定了一个点 $(x,y)$ ，那么 $(x,y)$ 到CD线段的一个点 $(x',y')$ 的距离加上 $(x',y')$ 到D点的时间显然是呈一个二次函数。于是我们可以在AB线段上枚举一个点，三分CD上的点，然后取最优即可。

但是，这样可能会超时，我们考虑点A到 $(x,y)$ 的时间随着距离增大而增大，这说明这里的函数是一条直线，那么显然 $(x,y)$ 也可以三分出来。这样时间复杂度是 $O(log_3^2L)$ （ L <script type="math/tex" id="MathJax-Element-8">L</script>是线段最长距离），所以是很快的。

Code

请自重！

#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);
}