题解 P2571 【[SCOI2010]传送带】

~~这道题用什么三分套三分、模拟退火算法啊，明明暴力都可以过~~ 很显然，从A走到D的最短路一定是在AB上走一段，在平面上走一段，再在CD上走一段，所以我们就可以枚举在AB走上的长度和在CD走上的长度 所以我们之间把AB和CD分成5000段，枚举走了几段就可以了 另外还要注意A，B点可能重合 __代码：__ ```cpp #pragma GCC optimize(2) #include<bits/stdc++.h> #define min(a,b) a>b?b:a using namespace std; int ax,ay,bx,by,cx,cy,dx,dy,p,q,r; double ll1,ll2; inline double dis(double x1,double x2,double yyy,double y2){ return sqrt((x1-x2)*(x1-x2)+(yyy-y2)*(yyy-y2)); //计算两点间的欧几里得距离 } inline double getVaule(double l1,double l2){ double x=double(ax)+l1/ll1*double(bx-ax),y=double(ay)+l1/ll1*double(by-ay); double xx=double(cx)+(ll2-l2)/dis(cx,dx,cy,dy)*double(dx-cx),yy=double(cy)+(ll2-l2)/ll2*double(dy-cy); if(bx==ax)x=0,y=0;//防止A,B点重合的情况 return l1/double(p)+dis(x,xx,y,yy)/double(r)+l2/double(q); //计算需要的时间 } #define gv getVaule int main(){ 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); ll1=dis(ax,bx,ay,by); ll2=dis(cx,dx,cy,dy); double l1=dis(ax,bx,ay,by)/5000,l2=dis(cx,dx,cy,dy)/5000,ans=1e8; for(register int i=0;i<=5000;i++){ for(register int j=0;j<=5000;j++){ ans=min(ans,getVaule(double(i)*l1,double(j)*l2)); } } //分成5000段然后枚举 printf("%0.2lf",ans); return 0; } ```