企业官网建设流程全解析

1. 这道“传送带”为什么值得反复咀嚼

做信息学竞赛的同学应该都有这种感觉：二分章节的题目，大部分都是“在一个有序数组里找一个数”“在单调函数上找一个零点”，套路很明显，练几道就上手了。但1439这道【SCOI2010】传送带，每次翻出来做，都觉得当初的自己太天真——它表面上是个几何题，实际考的是对二分和三分本质的理解，尤其是“什么时候二分不够用、必须上三分”的判断力。

我第一次做这题是在学完提高篇二分与三分之后，当时看完题面直接懵了：两根线段、三个速度、求最短时间，这哪跟哪？后来才知道，这道题是省内选拔的经典老题，被收录进基础算法提高篇，无数次出现在各种训练列表里，很多教练拿它当“二分与三分”章节的收尾题，就是因为它的思维跨度足够大。

这题适合谁做？如果你刚学完三分、对单峰函数极值还不熟，它是一道极好的巩固题；如果你自认为二分三分已经滚瓜烂熟，它也能让你重新审视一些细节。这篇东西我就把整道题从思路到实现，从头到尾拆一遍，包括踩过的精度坑、调试用的技巧、周边变式，一次性讲清楚。

1.1 先还原真实题面

平面直角坐标系里有两条线段AB和CD。一个人从A点出发，想到D点去。他在线段AB上走的速度是p，在线段CD上走的速度是q，在平面其他地方走的速度是r。注意这个“其他区域”指的是不在任何一条线段上的普通平面区域，包含从AB下来到CD上去的中间那段路。问从A到D最短需要多少时间。

输入给的是八个实数：A、B、C、D四个点的坐标，以及速度p、q、r。数据范围我记得大概是坐标绝对值不超过1000，速度都是正实数。输出最短时间，保留两位小数还是几位我记不太清，反正这道题的精度要求在当时看来确实刁钻，后面会说为什么。

很多人第一眼会想：这题是不是求一个折线路径，A到AB上某点，再到CD上某点，最后到D？没错，因为如果出口点不在AB上，那人在AB段外走的那一段速度是r；如果进CD之前已经在CD上了，那也不是最优的。理性分析就能发现，最优路径一定长这样：A出发在AB上走一段，离开AB后在平面区域走直线，到CD后再沿CD走到D。为什么中间必须是直线？平面区域速度恒定，两点之间直线时间最短，这是费马原理的朴素版，不需要证明，直觉上就能接受。

于是问题变成：在AB上选一个点E，在CD上选一个点F，让dist(A,E)/p + dist(E,F)/r + dist(F,D)/q最小。两个变量，两个约束，看起来很简单，但真正处理起来会发现，E和F互相影响，不是能独立优化的。

1.2 核心难点：双变量优化的拆解思路

上面那个式子如果只有一个变量，比如固定E求最优F，那问题立刻简化成一个一维优化。但两个变量同时变化，你没法直接“求导等于零”去解，因为你连解析式都写不出来，E和F都是二维坐标点。

竞赛里处理这种双变量问题有一个非常经典的思路：外层枚举一个变量，内层对另一个变量做精确优化。具体到这道题，就是外层三分E在AB上的位置，内层三分F在CD上的位置。说白了，对于AB上任意一个确定的E点，内层三分能找到一个让总时间最小的F点；而后把这个“最小时间”看成E的函数，这个函数它是个单谷函数——这一点是整道题能做的理论基石，也是需要证明或至少要有直观感受的。

为什么外层函数的单谷性可以保证？直观理解：E从A慢慢走向B，总时间先减小后增大。因为E太靠近A，浪费了AB上的高速区间；E太靠近B，E到F的平面距离会过长。中间某个位置平衡了“在AB上利用高速”和“减少平面路程”，时间最小。严谨证明需要用到凸函数复合的性质，竞赛里通常接受这个事实，但在心里要有数：三分的正确性完全依赖这个函数是单谷的。

2. 三分法原理再梳理：为什么不用二分

学二分的同学都熟悉一个场景：f(x)单调，可以二分找零点或找某个值。但如果函数不是单调的，而是一个先减后增的碗形（单谷），或者先增后减的包形（单峰），二分就失效了——你不知道该往左走还是往右走。这时候三分就派上用场了。

三分的思路非常直观。假设你在实轴上的区间[l, r]里找一个单谷函数的最小值点，你取两个中间点m1 = l + (r-l)/3和m2 = r - (r-l)/3，然后比较f(m1)和f(m2)：

• 如果f(m1) < f(m2)，说明最小值点不可能在m2右边，把右边界收缩到m2
• 反过来，最小值点不可能在m1左边，把左边界收缩到m1

每次迭代区间长度变为原来的2/3。如果你迭代60次，(2/3)^60大约是2.5e-11量级，配合双精度浮点，精度完全够用。这就是为什么很多模板里直接写“循环60次”而不是判断r-l > eps，因为循环次数固定能避免死循环，也更好控制误差。

2.1 三分和“带权三分、整数三分”的区别

很多同学在搜索引擎里搜“带权三分”或者“整数三分”，我估计是被其他题目误导了。所谓“带权三分”其实不是特殊算法，而是字面意思：三分时函数值带权重，比如求带权中位数之类的问题。而“整数三分”是在定义域是整数时用的。本题定义域是实数连续区间，坐标比例可以任意取值，所以直接用标准三分即可，不需要额外的离散化处理。

这里有一个容易犯迷糊的点：Abel上的点怎么参数化？用点的坐标(x, y)直接做三分变量行不行？严格说可以，但没必要，而且容易出错——你三分x，对应的y也变了，这是一个直线上的约束关系，函数值仍然是一维的，但你没把这个约束显式表达出来，写代码容易乱。更好的做法是用“比例”t ∈ [0, 1]，表示从A出发沿AB走了全程的百分之多少。这样每个t唯一对应一个点，而且三分区间固定是[0, 1]，简洁清晰。

这个参数化思路是我强烈建议新手养成的习惯：在一条线段上找点时，用一个归一化的比例值，而不是直接操作坐标。后面所有计算都通过getPoint(A, B, t)这个函数返回坐标，代码可读性和正确性都高很多。

2.2 时间复杂度预估

外层三分60次，每次算calc(t)；calc(t)内部又做60次内层三分。总计算量60 * 60 = 3600次函数求值，每次求值涉及三四个距离公式，也就是不到一万次sqrt运算。这个量级在竞赛环境下连零头都算不上，跑得飞快。

所以这道题别看思路绕，实现起来计算量很小，真正的难点在于把模型建对，以及把三分套三分写成清晰不犯错的结构。

3. 具体实现与核心代码

说一下我用C++从头实现这个题的全过程，包括每一段的意图和容易出错的地方。代码我会分块解释，不会一口气甩一大段让人自己啃。

3.1 坐标点与距离函数

#include <bits/stdc++.h> using namespace std; struct Point { double x, y; }; double dist(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }

这一段没什么好说的，就是最基础的结构体加距离公式。注意用double而不是float，这题的精度要求不允许你用单精度，稍后细说。

然后是关键的点在线段上按比例取位置：

Point getPoint(Point a, Point b, double t) { return {a.x + (b.x - a.x) * t, a.y + (b.y - a.y) * t}; }

t=0时返回A，t=1时返回B，t=0.5时是中点。用这个函数，三分出来的t直接映射成点坐标，干净利落。

3.2 内层三分：固定E求最优F

接下来定义计算函数。先说内层：给定AB上的E点，在CD上找一个F点，使得dist(E,F)/r + dist(F,D)/q最小。

注意这里为什么不含dist(A,E)/p？因为在外层计算时，E已经确定了，这一项是常数，不影响内层三分选择F。所以内层函数是：

double calcF(Point E, Point C, Point D, double q, double r) { double l = 0, rT = 1; for (int i = 0; i < 60; i++) { double m1 = l + (rT - l) / 3.0; double m2 = rT - (rT - l) / 3.0; Point F1 = getPoint(C, D, m1); Point F2 = getPoint(C, D, m2); double t1 = dist(E, F1) / r + dist(F1, D) / q; double t2 = dist(E, F2) / r + dist(F2, D) / q; if (t1 < t2) rT = m2; else l = m1; } Point bestF = getPoint(C, D, (l + rT) / 2.0); return dist(E, bestF) / r + dist(bestF, D) / q; }

内层三分判断的是CD上的比例，找到让“平面路程加CD内路程”最短的F点。我用了循环60次代替while (r-l > eps)，原因前面说了，固定次数更稳，不会因为eps设大了精度不够，也不会因为eps设小了死循环。

3.3 外层三分：寻找最优E

外层三分套上内层：

double solve() { // 已读入 A, B, C, D, p, q, r double l = 0, rT = 1; for (int i = 0; i < 60; i++) { double m1 = l + (rT - l) / 3.0; double m2 = rT - (rT - l) / 3.0; Point E1 = getPoint(A, B, m1); Point E2 = getPoint(A, B, m2); double t1 = dist(A, E1) / p + calcF(E1, C, D, q, r); double t2 = dist(A, E2) / p + calcF(E2, C, D, q, r); if (t1 < t2) rT = m2; else l = m1; } Point bestE = getPoint(A, B, (l + rT) / 2.0); return dist(A, bestE) / p + calcF(bestE, C, D, q, r); }

整体结构就是：外层三分枚举E，E确定后，内层三分完全求解F。三个速度都用上：p在AB段，q在CD段，r在中间平面段。代码里三分的名字rT我用了rT而不用r，避免和速度变量r冲突，这个细节在写完整代码时非常重要，变量名混乱是新手调试困难的一个主要来源。

3.4 完整代码参考

最终拼起来大概长这样，我整理成一个可以直接提交的版本：

#include <bits/stdc++.h> using namespace std; struct Point { double x, y; }; double dist(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } Point getPoint(Point a, Point b, double t) { return {a.x + (b.x - a.x) * t, a.y + (b.y - a.y) * t}; } double p, q, r; Point A, B, C, D; double calcF(Point E) { double l = 0, rt = 1; for (int i = 0; i < 60; i++) { double m1 = l + (rt - l) / 3.0; double m2 = rt - (rt - l) / 3.0; Point F1 = getPoint(C, D, m1); Point F2 = getPoint(C, D, m2); double t1 = dist(E, F1) / r + dist(F1, D) / q; double t2 = dist(E, F2) / r + dist(F2, D) / q; if (t1 < t2) rt = m2; else l = m1; } Point bestF = getPoint(C, D, (l + rt) / 2.0); return dist(E, bestF) / r + dist(bestF, D) / q; } double calcE(double t) { Point E = getPoint(A, B, t); return dist(A, E) / p + calcF(E); } int main() { scanf("%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y); scanf("%lf%lf%lf%lf", &C.x, &C.y, &D.x, &D.y); scanf("%lf%lf%lf", &p, &q, &r); double l = 0, rt = 1; for (int i = 0; i < 60; i++) { double m1 = l + (rt - l) / 3.0; double m2 = rt - (rt - l) / 3.0; double t1 = calcE(m1); double t2 = calcE(m2); if (t1 < t2) rt = m2; else l = m1; } printf("%.2lf\n", calcE((l + rt) / 2.0)); return 0; }

我补充一个个人习惯：把外层主干写成一个循环，内层逻辑全部封装成函数，这样主函数非常干净。如果比赛时时间紧张，直接套这个模板改改函数名就能用。

4. 精度控制与边界情况的实战经验

这道题最坑的不是思路，是精度。下面几条是我实际写起来踩过或者见过别人踩的坑，单列一节，希望能帮你少走弯路。

4.1 eps到底设多少

很多同学习惯写while (r - l > 1e-6)，在这题上可能出问题。因为三层运算叠加（外层三分+内层三分+距离计算），误差是会累积的。我实测过，如果内层用1e-6作为终止条件，外层也用1e-6，在一些极限数据下答案可能差到0.01以上，刚好卡在输出精度边界，非常被动。

稳妥做法是内层外层都用固定循环次数。我一般用60次迭代。为什么是60？因为(2/3)^60 ≈ 2.46e-11，这个精度远小于双重浮点数的极限精度，足够用了。就算比赛环境下的double精度是15位十进制数，60次迭代也把区间压到了极限，再多迭代也不会有收益。

如果你非要用while写法，建议eps用1e-12甚至更小，但要注意在极端情况下可能出现浮点数无法继续缩小的死循环，所以循环次数上限还是得加。这就回到了“固定次数”更稳妥的结论。

4.2 数据范围的边界：AB或CD退化成一个点

题目没说AB和CD一定是非退化的线段。如果A和B完全重合，或者C和D完全重合，三分照样能跑——因为区间[0,1]上的所有点都映射到同一个坐标，计算出来时间一样，三分不会出错。

但有一个地方需要小心：如果CD退化成一个点，内层三分的对象是恒定值，仍然能正常运行；如果AB退化成一个点，外层三分也同理。我测试过，代码在这两种退化情况下都能给出合理答案。但如果你输出精度要求高，退化情况下直接返回dist(A,D)/r（当AB和CD都退化成点，人也只能走平面）也可以特判，不过这属于锦上添花，不特判一般也不会挂。

4.3 三分区间必须是 [0,1]

由于我们用比例参数，区间天然是[0,1]。但有的同学会想：直接三分E点的x坐标不也行吗？如果AB是竖直线，x坐标恒定，三分就废了。所以再次强调比例参数化的优越性：无论线段方向如何，始终是一维区间上的问题，三分稳定。

如果你在别的问题里三分的是一个几何点的某个坐标，一定要先确认这个坐标和线段位置是一一映射且不退化，否则可能踩坑。

4.4 使用C++17或更高版本编译

代码里用了{a.x + ..., a.y + ...}这种聚合初始化结构体，在C++11及以后都支持。如果评测机是老古董编译器，可能需要改成构造函数。这个细节看起来不值一提，但我真有朋友因为本地C++17能过、评测机C++98直接ce的惨痛经历，所以提醒一句。

5. 常见问题与排查技巧

整理一下我在这道题上遇到的典型问题，以及和同学讨论时发现的高频错误。

除了表格里的，我再讲一个很隐蔽的bug：外层三分里计算t1时dist(A, E1) / p这一项，有的同学会写成dist(A, B) / p再乘以比例。这两种写法是一样的，但如果你混用了不同比例，比如用m1的E点却用m2的路径时间，那答案绝对错。这种错误非常隐蔽，样例数据简单时很可能测不出来，建议写完后在草稿纸上手动推一两个点验证。

还有一个高频问题：盲目套“三分求极大值”模板。有些讲义上三分模板是求最大值的，判断条件写反，直接抄过来最小值就变成了最大值。我建议每次写三分前默写一遍判断逻辑，别偷懒：如果是求最小值，f(m1) < f(m2)说明右边可以缩掉；求最大值则相反。这个方向和函数“碗形/包形”是对应的，理清楚再写，别硬背。

6. 延伸思考：这类“套娃三分”还能用在哪

这题做完之后，我觉得最值的不是学会套路，而是吃透“把嵌套问题拆成多个独立子问题”的思路。后面我在别的地方遇到不少相似的题，比如离线决策类DP、几何最短路径规划，本质都是这种“外层选一个决策，内层对另一个决策做精确求解”的结构。

稍微扩展一下：如果传送带的路径不是一条线段，而是一段圆弧，三分照样可以用——前提是参数化后目标函数仍然单峰。不过圆弧上的参数化就不能用简单的比例了，得用圆心角。另一个变式：如果中间平面区域速度也是变化的，比如存在障碍物，问题就直接升级成最短路加连续优化，性质会被打破，三分就不能硬用了。

这些延伸题我先不展开，但你做这道题时如果能养成“为什么单峰”“区间缩小的依据是什么”这样思考的习惯，后面进步会快很多。我个人做算法题最大的心得就是：一道好题，值得反复咀嚼，把每个“理所当然”的点都抠一遍，才能真正变成自己的东西。