「SCOI2010」传送带

题意：平面上有两条直线 $\text{AB,CD}$，你在 $\text{AB}$ 上的速度为 $p$，在 $\text{CD}$ 上的速度为 $q$，在直线外的速度为 $r$，现在你想从 $\text{A}$ 点走到 $\text{D}$ 点，最少要走多长时间？

数据范围与约定：对于 $100\%$ 的数据，$1\le x _{\text{A,B,C,D}},y _{\text{A,B,C,D}}\le 10 ^{3},1\le p,q,r\le 10$。

解析：三分套三分。先三分从 $\text{AB}$ 上离开的点，再三分到达 $\text{CD}$ 中的点，最后合起来即可。时间复杂度为 $O(\log |\text{AB}|\cdot \log |\text{CD}| )$。

#include<stdio.h>
#include<math.h>
int ax,ay,bx,by,cx,cy,dx,dy,p,q,r;
double lx,lr,rx,ry,lxm,lrm,rxm,rym,f1,f2;
double dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double three_devide_CD(double x,double y)
{
    double lx=cx;
    double ly=cy;
    double rx=dx;
    double ry=dy;
    double lxm,rxm,lym,rym,f1,f2;
    while(fabs(rx-lx)>1e-8||fabs(ry-ly)>1e-8)
    {
        lxm=lx+(rx-lx)/3;
        lym=ly+(ry-ly)/3;
        rxm=rx-(rx-lx)/3;
        rym=ry-(ry-ly)/3;
        f1=dis(ax,ay,x,y)/p+dis(x,y,lxm,lym)/r+dis(lxm,lym,dx,dy)/q;
        f2=dis(ax,ay,x,y)/p+dis(x,y,rxm,rym)/r+dis(rxm,rym,dx,dy)/q;
        if(f1>f2)
        {
            lx=lxm;
            ly=lym;
        }
        else
        {
            rx=rxm;
            ry=rym;
        }
    }
    return dis(ax,ay,x,y)/p+dis(x,y,lx,ly)/r+dis(lx,ly,dx,dy)/q;
}
double three_devide_AB(double x,double y)
{
    double lx=ax;
    double ly=ay;
    double rx=bx;
    double ry=by;
    double lxm,rxm,lym,rym,f1,f2;
    while(fabs(rx-lx)>1e-8||fabs(ry-ly)>1e-8)
    {
        lxm=lx+(rx-lx)/3;
        lym=ly+(ry-ly)/3;
        rxm=rx-(rx-lx)/3;
        rym=ry-(ry-ly)/3;
        f1=three_devide_CD(lxm,lym);
        f2=three_devide_CD(rxm,rym);
        if(f1>f2)
        {
            lx=lxm;
            ly=lym;
        }
        else
        {
            rx=rxm;
            ry=rym; 
        } 
    }
    return three_devide_CD(lx,ly);
}
int main()
{
    scanf("%d%d%d%d%d%d%d%d",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy);
    scanf("%d%d%d",&p,&q,&r);
    printf("%.2lf",three_devide_AB(ax,ay));
}