题解 P2571 【[SCOI2010]传送带】
swiftc
2019-09-14 14:27:12
~~这道题用什么三分套三分、模拟退火算法啊,明明暴力都可以过~~
很显然,从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;
}
```