直接复制以前写的代码,还带注释,真棒!
咳咳。
这道题,我们算从A到D点的最短距离,那么明显的,我们考虑三分。
我们先三分出从A点到AB中的某个点X,作为出发点,然后,再三分出从X到CD的某个点Y,再从Y直接到D,这样,我们就可以求出最小的值了。
我们来看看,我们这样三分是否完备。
我们走的最短路线一共有四种情况,即是否走两条传送带。
如果我们不走AB传送带,那么,其实就相当于一开始我们从A点走到A点,再开始走
不走CD传送带,也就是相当于直接从X走到D点(两点之间线段最短,且速度相同,所以不走CD传送带的话,直接走到D是最短的)
所以,我们发现,我们这样三分是完全可行的!做一遍就行了!
(代码看起来很长,但是大部分其实都是板子/重复的,具体看下函数这些就好了,基本有相应注释(以前的好习惯现在全丢了qwq))
由于doule具有精度问题,所以建议卡下精度
代码:
#include<cstdio>//三分大法无限好,脑壳痛的不得了~ @_@ #include<cmath> using namespace std;//方法:三分选取从AB上的哪个点开始,到CD上的哪个点,然后再从那个点到D点 const double eps=1e-4;//锁精度~ double ax,ay,bx,by,cx,cy,dx,dy; double P,Q,R; double a1,a2,b1,b2; inline void swap(double &x,double &y){ double c; c=x,x=y,y=c; } inline double f(double x,double a,double b){//已知x以及两系数,求y return a*x+b; } inline double far(double x,double y,double m,double n){//求两点之间的距离 return sqrt((x-m)*(x-m)+(y-n)*(y-n)); } inline double fi(double x,double y,double a,double b){ double tim=far(x,y,a,b)/R; tim+=far(x,y,dx,dy)/Q; return tim; } inline double suan(double x,double y){ double tim=far(x,y,ax,ay)/P;//A到(x,y)的时间 double l,r,ans,L,R; if(cx==dx){ l=cy,r=dy; if(l>r){ swap(l,r); } while(r-l>=eps){ double lx=l+(r-l)/3,rx=r-(r-l)/3; L=fi(cx,lx,x,y),R=fi(cx,rx,x,y); if(L<=R){ ans=L; r=rx; continue; } ans=R; l=lx; } return ans+tim; } l=cx,r=dx; if(l>r){ swap(l,r); } while(r-l>=eps){//三分由(x,y)到CD上的某点 double lx=l+(r-l)/3,rx=r-(r-l)/3; L=fi(lx,f(lx,a2,b2),x,y),R=fi(rx,f(rx,a2,b2),x,y); if(L<=R){ ans=L; r=rx; continue; } ans=R; l=lx; } return tim+ans; } int main(){ scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy); scanf("%lf%lf%lf",&P,&Q,&R); if(ax!=bx){ a1=(ay-by)/(ax-bx); b1=(ay-a1*ax); } if(cx!=dx){ a2=(cy-dy)/(cx-dx); b2=(cy-a2*cx); } double l,r,ans,L,R; if(ax==bx){ l=ay,r=by; if(l>r){ swap(l,r); } while(l<=r){ double lx=l+(r-l)/3,rx=r-(r-l)/3; L=suan(ax,lx),R=suan(ax,rx); if(L<=R){ ans=L; r=rx-eps; continue; } ans=R; l=lx+eps; } printf("%.2lf",ans); return 0; } l=ax,r=bx; if(l>r){ swap(l,r); } while(r-l>=eps){//三分由A到AB中的一点(不走AB即为从A到A) double lx=l+(r-l)/3,rx=r-(r-l)/3; L=suan(lx,f(lx,a1,b1)),R=suan(rx,f(rx,a1,b1)); if(L<=R){ r=rx; ans=L; continue; } l=lx; ans=R; } printf("%.2lf",ans); return 0; } /** * ┏┓ ┏┓+ + * ┏┛┻━━━┛┻┓ + + * ┃ ┃ * ┃ ━ ┃ ++ + + + * ████━████+ * ◥██◤ ◥██◤ + * ┃ ┻ ┃ * ┃ ┃ + + * ┗━┓ ┏━┛ * ┃ ┃ + + + +Code is far away from * ┃ ┃ + bug with the animal protecting * ┃ ┗━━━┓ 神兽保佑,代码无bug * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ + + + + * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛+ + + + */