【SCOI2010】【传送带】【三分答案】

题目大意

平面上有两条传送带，在上面行走有一定的速度，在平面其他地方行走有一定速度，求从一条传送带一端走到另一条一端的时间。

解题思路

显然在两条传送带都走一段后走平面，当一个转折点确定后，距离就是一个单峰函数，可以用三分解决，总的就是三分套三分。由于数据较小精度要求较小，可以暴力一个转折点再三分。

code

//#include<set> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define LF double #define LL long long #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) using namespace std; int const inf=2147483647; int ax,ay,bx,by,cx,cy,dx,dy,p,q,r; LF coun(LF x,LF y,LF xx){ LF yy=cy+((dx-cx)?(xx-cx)*(dy-cy)/(dx-cx):0); return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy))/r+sqrt((dx-xx)*(dx-xx)+(dy-yy)*(dy-yy))/q; } LF coun2(LF x,LF y,LF yy){ LF xx=cx; return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy))/r+sqrt((dx-xx)*(dx-xx)+(dy-yy)*(dy-yy))/q; } int main(){ freopen("d.in","r",stdin); freopen("d.out","w",stdout); scanf("%d%d%d%d",&ax,&ay,&bx,&by); scanf("%d%d%d%d",&cx,&cy,&dx,&dy); scanf("%d%d%d",&p,&q,&r); if(ax==bx){ swap(ax,ay); swap(bx,by); swap(cx,cy); swap(dx,dy); } LF lx=min(ax,bx),rx=max(ax,bx),bi=0.01,anss=inf; LF ansx=lx,ans=inf; for(LF x=lx;x<=rx;x+=bi){ LF y=ay+((bx-ax)?(x-ax)*(by-ay)/(bx-ax):0); if(cx!=dx){ LF ll=min(cx,dx),rr=max(cx,dx); for(;ll+1e-10<rr;){ LF m1=ll+(rr-ll)/3,m2=rr-(rr-ll)/3; if(coun(x,y,m1)+1e-10<coun(x,y,m2))rr=m2; else ll=m1; } if(sqrt((x-ax)*(x-ax)+(y-ay)*(y-ay))/p+coun(x,y,ll)<ans){ ans=sqrt((x-ax)*(x-ax)+(y-ay)*(y-ay))/p+coun(x,y,ll); ansx=x; } }else{ LF ll=min(cy,dy),rr=max(cy,dy); for(;ll+1e-10<rr;){ LF m1=ll+(rr-ll)/3,m2=rr-(rr-ll)/3; if(coun2(x,y,m1)+1e-10<coun2(x,y,m2))rr=m2; else ll=m1; } if(sqrt((x-ax)*(x-ax)+(y-ay)*(y-ay))/p+coun2(x,y,ll)<ans){ ans=sqrt((x-ax)*(x-ax)+(y-ay)*(y-ay))/p+coun2(x,y,ll); ansx=x; } } } anss=min(anss,ans); lx=max(ax*1.0,ansx-bi*30);rx=min(bx*1.0,ansx+bi*30);bi/=10; printf("%.2lf",anss); return 0; }