【SCOI2010】传送带

Description

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

Solution

一开始没有想到什么机智法，我三分出在AB上的一个点，然后直接走向D或垂直的。然而这样肯定是错的，可以水过好几个点，垂直的时候判断还很麻烦。

正解又短又机智

在三分AB上的一个点之后，再在CD上三分一个点就可以了。 很机智。

Code

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; typedef double db; double l,r,mid1,mid2,a,b,c,d; int ax,ay,bx,by,cx,cy,dx,dy,p,q,rr; db sin1,sin2,cos1,cos2,c1,c2,kx1,ky1,kx2,ky2,bbx2,bby2; db aa1,bb1,cc1,ans,ans1,x,y,yi,er,bbx1,bby1; db ju(db x,db y,db a,db b){ return sqrt((a-x)*(a-x)+(b-y)*(b-y)); } db suan1(db xx,db yy,db z){ db l=0,r=c2/q,mid1,mid2; db yi,er; while(r-l>1e-4){ mid1=l+(r-l)/3; mid2=l+2*(r-l)/3; x=kx2*mid1+bbx2,y=ky2*mid1+bby2; yi=ju(x,y,xx,yy)/rr+z+mid1; x=kx2*mid2+bbx2,y=ky2*mid2+bby2; er=ju(x,y,xx,yy)/rr+z+mid2; if(yi<er)r=mid2;else l=mid1; } x=kx2*l+bbx2,y=ky2*l+bby2; db ans=ju(x,y,xx,yy)/rr+z+l; return ans; } int main(){ scanf("%d%d%d%d",&ax,&ay,&bx,&by);c1=ju(ax,ay,bx,by); scanf("%d%d%d%d",&cx,&cy,&dx,&dy);c2=ju(cx,cy,dx,dy); scanf("%d%d%d",&p,&q,&rr); sin1=abs(by-ay)/c1;sin2=abs(dy-cy)/c2; cos1=abs(bx-ax)/c1;cos2=abs(dx-cx)/c2; kx1=cos1*p,ky1=sin1*p; bbx1=ax,bby1=ay; if(ax>bx)kx1=-kx1;if(ay>by)ky1=-ky1; kx2=cos2*q,ky2=sin2*q; bbx2=dx,bby2=dy; if(dx>cx)kx2=-kx2;if(dy>cy)ky2=-ky2; l=0,r=c1/p; while(r-l>1e-4){ mid1=l+(r-l)/3; mid2=l+2*(r-l)/3; x=kx1*mid1+bbx1,y=ky1*mid1+bby1; yi=suan1(x,y,mid1); x=kx1*mid2+bbx1,y=ky1*mid2+bby1; er=suan1(x,y,mid2); if(yi<er)r=mid2;else l=mid1; } x=kx1*l+bbx1,y=ky1*l+bby1; yi=suan1(x,y,l); printf("%.2f\n",yi); }