swift's blog

swift's blog

题解 P2571 【[SCOI2010]传送带】

posted on 2019-09-14 14:27:12 | under 题解 |

这道题用什么三分套三分、模拟退火算法啊,明明暴力都可以过

很显然,从A走到D的最短路一定是在AB上走一段,在平面上走一段,再在CD上走一段,所以我们就可以枚举在AB走上的长度和在CD走上的长度

所以我们之间把AB和CD分成5000段,枚举走了几段就可以了

另外还要注意A,B点可能重合

代码:

#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;
}