「SCOI2010」传送带 - 三分

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

在一个 \(2\) 维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段 \(\text{AB}\) 和线段 \(\text{CD}\)。lxhgww 在 \(\text{AB}\) 上的移动速度为 \(P\)，在 \(CD\) 上的移动速度为 \(Q\)，在平面上的移动速度 \(R\)。现在 lxhgww 想从 \(\text A\) 点走到 \(\text D\) 点，他想知道最少需要走多长时间。

解题思路

我们先忽略 \(\text{CD}\) 线段，很明显我们在 \(\text{AB}\) 上行走的距离与时间呈现一个单谷函数，故我们可以使用三分解决该问题。

接下来我们考虑 \(\text{CD}\) 线段，这时候我们可以用三分套三分来解决该问题。第一个三分解决在哪个位置从 \(\text{AB}\) 下来，下来后的坐标可利用第二个三分求从该坐标出发到 \(\text D\) 的最短时间，即在哪从地面上到 \(\text{CD}\)。时间复杂度为 \(O(\log_3^2 n)\)

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cmath>
#include <iostream>
#include <utility>

double ax, ay, bx, by;
double cx, cy, dx, dy;
double p, q, rr;

double dis(std::pair<double, double> a, std::pair<double, double> b) {
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

double solveCD(double x, double y) {
    std::pair<double, double> l = std::make_pair(cx, cy), r = std::make_pair(dx, dy);
    std::pair<double, double> lMid, rMid;
    double lVal = -100, rVal = dis(std::make_pair(ax, ay), std::make_pair(dx, dy)) / rr;

    while (std::abs(rVal - lVal) >= 0.000001) {
        lMid = std::make_pair(l.first + (r.first - l.first) / 3.0, l.second + (r.second - l.second) / 3.0);
        rMid = std::make_pair(l.first + (r.first - l.first) / 1.5, l.second + (r.second - l.second) / 1.5);
        lVal = dis(lMid, std::make_pair(x, y)) / rr + dis(lMid, std::make_pair(dx, dy)) / q;
        rVal = dis(rMid, std::make_pair(x, y)) / rr + dis(rMid, std::make_pair(dx, dy)) / q;

        if (lVal > rVal) l = lMid;
        if (lVal < rVal) r = rMid;
        if (lVal == rVal) l = lMid, r = rMid;
    }

    return lVal;
}

double solveAB() {
    std::pair<double, double> l = std::make_pair(ax, ay), r = std::make_pair(bx, by);
    std::pair<double, double> lMid, rMid;
    double lVal = -100, rVal = dis(std::make_pair(ax, ay), std::make_pair(bx, by)) / p;

    while (std::abs(rVal - lVal) >= 0.000001) {
        lMid = std::make_pair(l.first + (r.first - l.first) / 3.0, l.second + (r.second - l.second) / 3.0);
        rMid = std::make_pair(l.first + (r.first - l.first) / 1.5, l.second + (r.second - l.second) / 1.5);
        lVal = dis(lMid, std::make_pair(ax, ay)) / p + solveCD(lMid.first, lMid.second);
        rVal = dis(rMid, std::make_pair(ax, ay)) / p + solveCD(rMid.first, rMid.second);

        if (lVal > rVal) l = lMid;
        if (lVal < rVal) r = rMid;
        if (lVal == rVal) l = lMid, r = rMid;
    }

    return lVal;
}

int main() {
    std::cin >> ax >> ay >> bx >> by;
    std::cin >> cx >> cy >> dx >> dy;
    std::cin >> p >> q >> rr;

    printf("%.2f\n", solveAB());

    return 0;
}