形式化题目

平面上有两条线段 $AB$ 与 $CD$，各看成一条传送带。在 $AB$ 上移动的速度为 $P$，在 $CD$ 上移动的速度为 $Q$，在平面其余位置移动的速度为 $R$。人从 $A$ 出发要走到 $D$，每一步走哪条路线都由自己决定，求最短总时间。

样例（$A=(0,0)$，$B=(0,100)$，$C=(100,0)$，$D=(100,100)$，$P=Q=2$，$R=1$）的最优路线如下图：绿色是沿 AB 的 $A\to X$ 段，蓝色是直线飞行的 $X\to Y$ 段，橙色是沿 CD 的 $Y\to D$ 段。

先看路线形状：人只在两条竖直传送带附近活动，中间一大段是斜穿平面的直线飞行。整条路线恰好由"沿 AB 走一段 + 直线飞行 + 沿 CD 走一段"组成，其中下车点 $X$、上车点 $Y$ 的位置是仅有的两个自由决策。对照数字：完全不踩传送带直飞要 $141.42$ 秒，而这条三段式路线只要 $136.60$ 秒——传送带把两头"顺路"的距离提速了。

正解

思路

第一步：最优路线一定可以写成三段。 在 $AB$ 上走到某个点 $X$ 下车，直线飞到 $CD$ 上的某个点 $Y$，再沿 $CD$ 走到 $D$：

三点理由：

• 中间一段以恒定速度 $R$ 移动，两点之间显然直线最短；
• 不会"离开传送带又回来"：若某走法离开 $AB$ 兜一圈再回到 $AB$，由三角不等式，把兜圈的那部分换成"直接沿 $AB$ 走"或"直接飞过缺口"（两者取快）不会更慢，逐段替换后每条传送带至多用一整段；
• 传送带若比飞行还慢（比如 $P<R$），最优解干脆整条不用——这正好对应 $X=A$ 或 $Y=D$ 的端点取值，不需要特判。

于是决策只剩两个连续参数。令 $X(t)=A+t(B-A)$，$Y(s)=C+s(D-C)$，$t,s\in[0,1]$，总时间为

"不用传送带直飞"也在这族路线里：取 $t=0$、$s=1$ 即可。把 $t,s$ 各离散成 $n$ 个点做 $O(n^2)$ 枚举既慢又不满足精度，连续决策点应当用连续优化的手段——三分搜索。

第二步：固定下车点，上车点可以三分。 固定 $t$，把 $s$ 看成自变量。"沿一条直线匀速移动的点到一个定点的距离"是参数的凸函数——单调段加 V 形转弯，是标准的单峰形态；而两个凸函数相加仍是凸函数，所以

关于 $s$ 凸，可以先对 $s$ 实数三分，求出固定 $t$ 时的最短时间。

第三步：整体再对下车点三分。 外层想三分的函数是

一般的"凸函数取 $\min$"并不保凸，这里能用三分的关键是：$T(t,s)$ 的三项都是"仿射映射与范数的复合"，例如 $X(t)-Y(s)=(A-C)+t(B-A)-s(D-C)$ 是 $(t,s)$ 的仿射映射，另外两项各自只含一个变量。三者相加，$T$ 关于 $(t,s)$ 是联合凸的；而联合凸函数对一个变量取最小（部分最小化）后仍然是凸函数，所以 $F(t)$ 凸，可以对 $t$ 再做三分。

两步合起来就是嵌套三分：外层三分下车点 $t$，每到一个 $t$ 就内层三分上车点 $s$。三分模板每次取

若 $f(m_1)<f(m_2)$ 则最小值不在 $(m_2,hi]$（凸性保证），令 $hi=m_2$，否则令 $lo=m_1$，区间每轮缩成原来的 $\tfrac{2}{3}$。

下表展示样例中固定 $t=t^\ast=0.368$ 后，内层对上车点参数 $s$ 三分的前 5 轮（$f$ 即固定 $t$ 的总时间）：

每一轮都是右边的试探点更优，于是左端不断右移，最小值被夹在 $[lo,hi]$ 里：5 轮后区间宽从 $1$ 缩到约 $0.13$，60 轮后 $(2/3)^{60}\approx 4\times 10^{-11}$。代码里固定跑 100 轮（$(2/3)^{100}\approx 2.5\times 10^{-18}$），随后直接取中点求值，远高于保留两位小数所需的 $0.005$ 精度，也不会死循环。

顺带一提，样例里外层 $F(t)$ 在 $t\in[0,0.37]$ 上是一段平台：AB、CD 是两条平行的竖直传送带时，存在一整族等价的最优上下车组合。三分遇到平台时 $f(m_1)=f(m_2)$，走 $lo=m_1$ 分支继续收缩，最终落在平台内任意点，返回的最小值不受影响。

代码

Python 版：

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 10:23
# update_at: 2026-09-30 10:34

import sys
from collections.abc import Callable
from math import hypot

Point = tuple[float, float]

A: Point = (0.0, 0.0)  # 起点，也是 AB 的左端点
B: Point = (0.0, 0.0)  # AB 的右端点
C: Point = (0.0, 0.0)  # CD 的左端点
D: Point = (0.0, 0.0)  # 终点，也是 CD 的右端点
P = 1.0                # AB 上的移动速度
Q = 1.0                # CD 上的移动速度
R = 1.0                # 平面上（不踩传送带）的移动速度


def dist(u: Point, v: Point) -> float:
    """两点间的欧氏距离。"""
    return hypot(u[0] - v[0], u[1] - v[1])


def on_seg(seg: tuple[Point, Point], t: float) -> Point:
    """线段上参数为 t 的点：t=0 是起点，t=1 是终点。"""
    (x1, y1), (x2, y2) = seg
    return (x1 + t * (x2 - x1), y1 + t * (y2 - y1))


def belt_time(t: float, s: float) -> float:
    """走 A →X(t)→Y(s)→ D 的总时间：AB 段速度 P、中途飞行 R、CD 段速度 Q。"""
    x = on_seg((A, B), t)  # 在 AB 上的下车点
    y = on_seg((C, D), s)  # 在 CD 上的上车点
    return dist(A, x) / P + dist(x, y) / R + dist(y, D) / Q


def ternary_min(f: Callable[[float], float], lo: float, hi: float) -> float:
    """对 [lo, hi] 上的单峰（凸）函数 f 做实数三分，返回最小值。"""
    for _ in range(100):
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2):
            hi = m2
        else:
            lo = m1
    return f((lo + hi) / 2)


def entry_time(t: float) -> float:
    """固定 AB 上的下车点 X(t)，选好 CD 上的上车点后能达到的最短全程时间。"""
    return ternary_min(lambda s: belt_time(t, s), 0.0, 1.0)


def minimum_time() -> float:
    """全程最短时间：外层三分下车点，内层三分上车点。"""
    return ternary_min(entry_time, 0.0, 1.0)


def solve() -> None:
    """读入坐标与速度，输出 A 到 D 的最短时间，保留两位小数。"""
    global A, B, C, D, P, Q, R
    ax, ay, bx, by, cx, cy, dx, dy, p, q, r = map(float, sys.stdin.buffer.read().split())
    A, B, C, D = (ax, ay), (bx, by), (cx, cy), (dx, dy)
    P, Q, R = p, q, r
    print(f"{minimum_time():.2f}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 01:08
 * update_at: 2026-10-05 01:08
 */

// 最优路线一定是三段：A ->X(在AB上)-> Y(在CD上)-> D。
// 固定下车点 X 时，总时间关于上车点参数 s 是凸函数，可以内层三分；
// T(t,s) 联合凸，对 s 取最小后 F(t) 仍凸，外层再对下车点参数 t 三分。
// 嵌套实数三分，O(log^2(1/eps)) 求最小时间。

#include <cstdio>
#include <cmath>

typedef long long ll;

double ax, ay, bx, by; // 线段 AB 两端坐标（A 是起点）
double cx, cy, dx, dy; // 线段 CD 两端坐标（D 是终点）
double P, Q, R;        // 分别是 AB 上、CD 上、平面上的移动速度

const int ROUND = 100; // 三分固定迭代轮数，(2/3)^100 远小于所需精度

// 两点间欧氏距离
double dist(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

// 走 A -> X(t) -> Y(s) -> D 的总时间
// t, s 分别是 X 在 AB 上、Y 在 CD 上的参数（0 是线段起点，1 是终点）
double total_time(double t, double s) {
    double px = ax + t * (bx - ax); // 下车点 X 的坐标
    double py = ay + t * (by - ay);
    double qx = cx + s * (dx - cx); // 上车点 Y 的坐标
    double qy = cy + s * (dy - cy);
    return dist(ax, ay, px, py) / P
         + dist(px, py, qx, qy) / R
         + dist(qx, qy, dx, dy) / Q;
}

// 固定下车点参数 t，对上车点参数 s 三分求最短时间
double inner_min(double t) {
    double lo = 0.0, hi = 1.0;
    for (int i = 1; i <= ROUND; ++i) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (total_time(t, m1) < total_time(t, m2))
            hi = m2;
        else
            lo = m1;
    }
    return total_time(t, (lo + hi) / 2);
}

// 外层对下车点参数 t 三分，求全程最短时间
double outer_min() {
    double lo = 0.0, hi = 1.0;
    for (int i = 1; i <= ROUND; ++i) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (inner_min(m1) < inner_min(m2))
            hi = m2;
        else
            lo = m1;
    }
    return inner_min((lo + hi) / 2);
}

int main() {
    scanf("%lf %lf %lf %lf", &ax, &ay, &bx, &by);
    scanf("%lf %lf %lf %lf", &cx, &cy, &dx, &dy);
    scanf("%lf %lf %lf", &P, &Q, &R);
    printf("%.2f\n", outer_min());
    return 0;
}

复杂度

• 时间复杂度：内层 100 轮、每轮 2 次求值，外层再套 100 轮，总共约 $100\times 201\approx 2\times 10^4$ 次 $T(t,s)$ 求值，即 $O(\log^2(1/\varepsilon))$（$\varepsilon$ 为目标精度），与坐标大小无关。Python 实测每组数据约 $0.03$ 秒。
• 空间复杂度：$O(1)$，只保存 8 个坐标、3 个速度和三分的区间端点。

总结

• 建模核心是把自由走法压缩成三段式路线 $A\to X\to Y\to D$：直线段由"恒速走直线最短"保证，"反复上下传送带不更优"由三角不等式保证，"传送带没用"则被端点 $t=0$、$s=1$ 自然吸收。
• 两个连续决策点各配一层三分；外层能三分的依据必须说准——$T(t,s)$ 联合凸，部分最小化保凸，而不是含糊的"取 min 后还是凸的"。
• 实数三分模板：每轮比较 $f(m_1),f(m_2)$ 缩区间到 $2/3$，固定迭代次数后取中点求值；相等时单侧收缩，天然兼容函数平台。
• 样例对照：直飞 $141.42$s，只用 AB 的最优 $136.62$s，两段都用 $136.60$s，可见"两头搭传送带"的收益是逐段累加的。