题解 P2571 【[SCOI2010]传送带】

· · 题解

表示蒟蒻并不会楼下的什么三分套三分退火啊粒子群啊……只能暴力了……

我是这样做的，把每一条线段平均拆成5000个点，然后两条线段上的点对之间两两匹配，取时间最小的

然后之后我交了一发三分竟然WA了

所以暴力才是最正确的方法

//minamoto
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
double x[N+5],y[N+5],xx[N+5],yy[N+5];
double t1[N+5],t2[N+5];
inline double dis(int i,int j){return sqrt((x[i]-xx[j])*(x[i]-xx[j])+(y[i]-yy[j])*(y[i]-yy[j]));}
double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,p,q,r,ans=1e18;
int main(){
//  freopen("testdata.in","r",stdin);
//  freopen("transporter.in","r",stdin);
//  freopen("transporter.out","w",stdout);
    cin>>Ax>>Ay>>Bx>>By>>Cx>>Cy>>Dx>>Dy>>p>>q>>r;
    double dx=(Bx-Ax)/N,dy=(By-Ay)/N;
    for(int i=0;i<=N;++i){
        x[i]=Ax+dx*i,y[i]=Ay+dy*i;
        t1[i]=sqrt(dx*i*dx*i+dy*i*dy*i)/p;
    }
    dx=(Dx-Cx)/N,dy=(Dy-Cy)/N;
    for(int i=0;i<=N;++i){
        xx[i]=Dx-dx*i,yy[i]=Dy-dy*i;
        t2[i]=sqrt(dx*i*dx*i+dy*i*dy*i)/q;
    }
    for(int i=0;i<=N;++i)for(int j=0;j<=N;++j)
    ans=min(ans,t1[i]+t2[j]+dis(i,j)/r);
    printf("%.2lf\n",ans);return 0;
}