洛谷2571 [SCOI2010]传送带

我们假设在 $AB$ 段走到 $M$ 点，然后走到 $CD$ 段的 $N$ 点，那么可以得到时间为

$$T= \dfrac {AM}{P} + \dfrac {MN}{R} + \dfrac {ND}{Q}$$

很显然我们的目标就是找到合适的 $M$ 和 $N$ 让时间最小。

对于 $M$ ，如果我们知道 $k= \dfrac {AM}{AB}$ ，那么就可以确定 $M$ 的坐标为

$$M(A_x+(B_x-A_x)\times k,A_y+(B_y-A_y)\times k)$$

将我们枚举的 $k$ 视为自变量，可以得到 $AM$ 的距离

$$AM = \dfrac {\sqrt {(B_x-A_x)^{2}+(B_y-A_y)^{2}}}{P} \times k$$

很显然是一个一次函数，如果我们确定了 $N(x_0,y_0)$，就可以计算 $MN$ 的距离的平方值

$$MN^{2} = \left[ (1-k)\times A_x + k\times B_x - x_0 \right]^{2} + \left[ (1-k)\times A_y + k\times B_y - y_0 \right]^{2}$$

通过整理可以得到右边的二次项其实是

$$\left[ (B_x-A_x)^{2} + (B_y-A_y)^{2}\right] \times k^{2}$$

是一个二次函数并且开口朝上，开根后再加上之前计算的 $AM$ 的值形状还是不变，所以可以用三分来求。

对于 $N$ 也同理，再套一次三分就可以求得答案了。

#define eps 1e-5

double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,p,q,r;

inline double get_dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

inline double check2(double k1,double k2)
{
    double Mx=Ax+(Bx-Ax)*k1,My=Ay+(By-Ay)*k1,Nx=Cx+(Dx-Cx)*k2,Ny=Cy+(Dy-Cy)*k2;
    return get_dis(Ax,Ay,Mx,My)/p+get_dis(Mx,My,Nx,Ny)/r+get_dis(Nx,Ny,Dx,Dy)/q;
}

inline double check(double k)
{
    double l=0,r=1;
    while (r-l>eps)
    {
        double r_mid=(l+r)/2,l_mid=(l+r_mid)/2;
        if (check2(k,r_mid)>check2(k,l_mid)) r=r_mid;
        else l=l_mid;
    }
    return check2(k,l);
}

int main()
{
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&Ax,&Ay,&Bx,&By,&Cx,&Cy,&Dx,&Dy,&p,&q,&r);
    double l=0,r=1;
    while (r-l>eps)
    {
        double r_mid=(l+r)/2,l_mid=(l+r_mid)/2;
        if (check(r_mid)>check(l_mid)) r=r_mid;
        else l=l_mid;
    }
    printf("%.2f",check(l));
    return 0;
}