题解 P2571 【传送带】

· · 题解

题意简述

求从A点到D点的最短时间。

输入：

输出：

题目分析

首先来看看样例。

点 E 为线段 AB 上的任意一点，点 F 为线段 CD 上的任意一点，从 A 到 D 所用时间最短的路线显然就是 \frac{AE}{P}+\frac{DF}{Q}+\frac{EF}{R} 的最小值。

假如 E 是定点，那么要找最优的 F 点，很容易就能想到三分。

而现在 E 点也是动点，所以我们对点 E 也使用三分，即三分套三分，这样即可找到最优解。

那么该如何进行三分呢？

首先三分需要 midl 和 midr ，这里使用的 midl、midr 有些特别。为了便于计算距离以及对区间进行三等分，需要记录点的坐标，当 midl 与 midr 横纵坐标都相同时才停止三分。为了避免 B 在 A 的左边这样的问题，在做减法的时候需要使用fabs。

在寻找点 E 的时候，缩小范围时判断 midl 与 midr 哪个能找到更优的 F，而在寻找点 F 时，缩小范围则要判断哪个所用的时间最少。

详情请见代码：

#include <bits/stdc++.h>
using namespace std;
double ax, ay, bx, by, cx, cy, dx, dy;                           //A、B、C、D点的坐标
double P, Q, R;                                                  //速度
inline double getDis(double x1, double y1, double x2, double y2) //用于获取两点距离
{
    return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
inline double getTime(double x1, double y1, double x2, double y2) //获取所需的时间
{
    double a = getDis(x1, y1, ax, ay); //E点到A点的距离
    double b = getDis(x2, y2, dx, dy); //F点到D点的距离
    double c = getDis(x1, y1, x2, y2); //E点到F点的距离
    return a / P + b / Q + c / R;      //计算时间
}
double searchCD(double xx, double yy) //枚举CD上的点F
{
    double lx, rx, ly, ry;                                 //当前左右端点的横纵坐标
    double midlx, midrx, midly, midry;                     //即midl和midr的横纵坐标
    lx = cx, rx = dx, ly = cy, ry = dy;                    //左边界设置为C的坐标，右边界设置为D的坐标
    while (fabs(rx - lx) > 1e-10 or fabs(ry - ly) > 1e-10) //横纵坐标都相同才停止
    {
        /*三等分横纵坐标*/
        midlx = lx + (rx - lx) / 3.f;
        midrx = rx - (rx - lx) / 3.f;
        midly = ly + (ry - ly) / 3.f;
        midry = ry - (ry - ly) / 3.f;

        if (getTime(xx, yy, midlx, midly) < getTime(xx, yy, midrx, midry)) //左边的的更优就向左
        {
            rx = midrx;
            ry = midry;
        }
        else //否则向右
        {
            lx = midlx;
            ly = midly;
        }
    }
    return getTime(xx, yy, midlx, midry); //返回当前的最优解
}
double searchAB() //枚举AB上的点E
{
    double lx, rx, ly, ry;                                 //当前左右端点的横纵坐标
    double midlx, midrx, midly, midry;                     //即midl和midr的横纵坐标
    lx = ax, rx = bx, ly = ay, ry = by;                    //左边界设置为A的坐标，右边界设置为B的坐标
    while (fabs(rx - lx) > 1e-10 or fabs(ry - ly) > 1e-10) //横纵坐标都相同才停止
    {
        /*三等分横纵坐标*/
        midlx = lx + (rx - lx) / 3.f;
        midrx = rx - (rx - lx) / 3.f;
        midly = ly + (ry - ly) / 3.f;
        midry = ry - (ry - ly) / 3.f;

        if (searchCD(midlx, midly) < searchCD(midrx, midry)) //左边的的更优就向左
        {
            rx = midrx;
            ry = midry;
        }
        else //否则向右
        {
            lx = midlx;
            ly = midly;
        }
    }
    return searchCD(lx, ly); //返回得到的结果
}
int main()
{
    /*输入*/
    cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy;
    cin >> P >> Q >> R;

    /*输出*/
    printf("%.2f\n", searchAB());
    return 0;
}