[SCOI2010]传送带 题解

直接复制以前写的代码，还带注释，真棒！

咳咳。

这道题，我们算从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　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/