CF1666C “Connect the Points” 是 Codeforces 上一道非常典型的构造题。题目名听着像图论实际上它考的是曼哈顿距离下的最小连接网络核心突破口就一句话三个点之间想要连通最优方案的长短其实被它们的包围盒完全锁死了。这篇文章我会从第一反应开始讲把这道题的思路、证明、代码和边界坑全部过一遍适合刚接触构造题、想练“怎么证明一个方案是最优”的选手参考。1. 看懂题目不是让你画曼哈顿最小生成树1.1 题目在说什么给平面上三个点坐标都是整数。你可以画若干条线段要求每条线段要么水平、要么垂直最终让这三个点处于同一个连通块里。注意这里说的是线段不是直线所以每条线段都有明确端点。你需要最小化所有线段的总长度然后输出一种合法方案。输出格式是先输出线段条数 k再输出 k 行每行四个整数表示一条线段的两个端点坐标。这题的坑点在于它没有限制你必须用几条线段也不限制线段之间能不能相交、能不能共享端点。你完全可以画一个很复杂的网格把三个点串起来但那样总长度会爆炸。题目要的是所有方案里总长度最小的那一类然后你随便输出其中一个就通过。坐标范围我记不清具体数值但印象中绝对值能到 1e9 这个量级所以计算总长度时用 int 有风险直接开 long long 最稳。输出端点的顺序没有要求你可以把线段的两个端点写成任意顺序Special Judge 只关心这几条线段是否合法、是否连通、总长度是否达到了理论最小值。1.2 第一反应为什么容易翻车我第一次看这题的时候脑子里跳出来的想法是这不就是求三个点在曼哈顿距离下的最小生成树吗把三个点两两之间的距离算出来跑一个 MST然后把 MST 里的每条边拆成一条水平线段和一条垂直线段画出来。这个思路看着合理实际上很容易画出一堆多余的线段。举个反例三个点分别是 (0,0)、(4,6)、(10,2)它们两两的曼哈顿距离分别是 10、8、6MST 会选择长度为 6 的边 (4,6)-(10,2) 和长度为 8 的边 (0,0)-(4,6)算一下(0,0) 到 (4,6) 是 10(4,6) 到 (10,2) 是 8(0,0) 到 (10,2) 是 10不对|0-10||0-2|12。那么 MST 边长为 8 和 10总长 18。但真实最优是 16比 MST 的结果短。问题出在曼哈顿 MST 里的每条边都走 L 形路径两条 L 形路径之间不一定能共享线段导致总长度变大。还有的人会想到直接枚举三种 L 形连接方式比如从点 A 先横后竖连到点 B再从点 B 先竖后横连到点 C。这样做得到的长度也是一个固定值但同样不一定最优因为你没有利用“三条路径可以共享同一条水平线”这个关键性质。所以这道题真正要解决的问题是能不能找到一个网络它的形状足够简单同时长度恰好等于一个谁都突破不了的下界。说白了就是“证明下界然后画一个刚好碰到下界的图形”。2. 先证下界答案被包围盒卡死了2.1 水平方向的最小花费设三个点的横坐标分别是 x1、x2、x3记录 Xmin min(x1,x2,x3)Xmax max(x1,x2,x3)。再设 Ymin、Ymax 同理。先单独看水平方向。任意一个合法的连接方案里所有水平线段加起来的长度和一定至少是 Xmax - Xmin。为什么因为最后整个图形是连通的那么横坐标最小的那个点和横坐标最大的那个点它们之间一定存在一条路径。这条路径上所有水平方向的位移绝对值加起来肯定不会小于 Xmax - Xmin。你想从横坐标 Xmin 的点出发沿着一堆水平和垂直线段走到横坐标 Xmax 的点你在水平方向上无论如何都要完成一段从 Xmin 到 Xmax 的净位移。哪怕中途来回绕路水平位移的绝对值总和只会比直线距离更大。而整个方案里的所有水平线段长度总和又一定覆盖了这条路径上的水平位移。所以所有水平线段长度之和 ≥ Xmax - Xmin。2.2 垂直方向同理长度被卡死在XspanYspan垂直方向完全对称。纵坐标最小的点和纵坐标最大的点之间一定存在路径这条路径上的垂直位移绝对值之和至少是 Ymax - Ymin所以所有垂直线段长度之和 ≥ Ymax - Ymin。把两个不等式加起来任意合法方案的总长度一定满足总长度 ≥ (Xmax - Xmin) (Ymax - Ymin)。这个下界只和三个点的包围盒有关和点在这个包围盒里的具体位置完全无关。也就是说不管三个点怎么摆只要它们围出来的横向跨度是 10、纵向跨度是 6那任何方案的线段总长度都不可能低于 16。这个结论非常强它直接告诉我们最优解不可能低于这个值。接下来只要构造出一个总长度正好等于这个下界的方案就等于找到了最优解。3. 构造方案一条水平主线加两条竖线3.1 为什么是y的中位数现在问题变成怎么画才能让水平线段总长度恰好是 Xmax - Xmin垂直线段总长度恰好是 Ymax - Ymin一个很自然的想法是先画一条水平线横跨整段 Xmin 到 Xmax长度就是 Xmax - Xmin。那么这条线应该放在哪个高度如果三个点全在这条水平线上那就一步到位了。可惜一般情况下三个点的 y 坐标各不相同不可能全落在一条水平线上。这时候就需要选一个合适的 y 值让大多数点可以通过一条竖线接到这条水平线上。如果选 y 为三个 y 坐标的中位数也就是排序后中间那个数那么三个点里至少有一个点的 y 正好等于这个中位数另外两个点一个在中位数上方、一个在中位数下方也可能有相等相等就更好。这样一来画竖线连接每个“不在水平线上的点”时每个点只需要画一条竖线。而且因为中位数把另外两个点分在了两侧这些竖线不会出现多余的重复覆盖竖线总长度刚好等于 Ymax - Ymin。你可以算一下竖线总长度等于所有 |yi - ym| 的和当 ym 是 y 的中位数时这个和恰好是 Ymax - Ymin不多不少。这就是中位数在这题里不可替代的原因。如果你取平均值三个点的 y 平均值可能在上下两个点之间但没有任何一个点正好落在这个平均值上三条线都要单独画竖线长度可能也还是 Ymax - Ymin但至少你享受不到“有一个点已经在水平线上”的便利。更关键的是平均值不保证让上下两侧的点数量均衡容易出现一条竖线被另一条竖线覆盖一部分的情况输出方案会变得奇怪。3.2 完整构造流程与手算例子具体构造分三步把三个点的 x 坐标排序得到 Xmin、Xmid、Xmax。我们暂时不关心 Xmid但后面证明会用到它。把三个点的 y 坐标排序令 ym 中间那个 y 值。先输出一条水平线段端点是 (Xmin, ym) 和 (Xmax, ym)。对每一个原始点 (xi, yi)如果 yi ≠ ym就输出一条竖直线段端点是 (xi, yi) 和 (xi, ym)。来看我之前举的例子三个点 (0,0)、(4,6)、(10,2)。x 排序后是 0、4、10所以 Xmin0、Xmax10。y 排序后是 0、2、6所以 ym2。先画水平线段 (0,2) 到 (10,2)长度 10。然后检查每个点(0,0) 不在 y2 上画竖线 (0,0) 到 (0,2)长度 2(4,6) 不在 y2 上画竖线 (4,6) 到 (4,2)长度 4(10,2) 已经在水平线上不画额外竖线。总长度 10 2 4 16正好等于 Xspan10 加上 Yspan6。从图形上看就是一条贯穿左右的水平线下面飘着一个点就拉一根竖线下来上面飘着一个点就拉一根竖线上去。因为水平线的高度选在了 y 的中位数所以下面的点和上面的点恰好各不超过一个整个图形最多只有三条线段非常干净。这个方案显然连通所有竖线都接在水平线上水平线又把所有竖线的根部连在一起所以三个点最终在一个连通块里。4. 代码实现排序、取中位、特判共线4.1 C17参考代码#include bits/stdc.h using namespace std; using ll long long; struct Point { ll x, y; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); vectorPoint p(3); for (int i 0; i 3; i) { cin p[i].x p[i].y; } vectorll xs, ys; for (int i 0; i 3; i) { xs.push_back(p[i].x); ys.push_back(p[i].y); } sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end()); ll Xmin xs[0], Xmax xs[2]; ll Ymin ys[0], Ymax ys[2]; ll ym ys[1]; // 三个点完全相同 if (Xmin Xmax Ymin Ymax) { cout 0 \n; return 0; } // 三个点竖直共线 if (Xmin Xmax) { cout 1 \n; cout Xmin Ymin Xmax Ymax \n; return 0; } // 三个点水平共线 if (Ymin Ymax) { cout 1 \n; cout Xmin Ymin Xmax Ymax \n; return 0; } vectorarrayll, 4 segs; // 水平主线 segs.push_back({Xmin, ym, Xmax, ym}); // 每个不在水平线上的点拉一条竖线到水平线 for (int i 0; i 3; i) { if (p[i].y ! ym) { segs.push_back({p[i].x, p[i].y, p[i].x, ym}); } } cout segs.size() \n; for (auto s : segs) { cout s[0] s[1] s[2] s[3] \n; } return 0; }这段代码的流程很直接先读点然后分别对 x 和 y 排序取出 Xmin、Xmax、Ymin、Ymax、ym。之后分三种特殊情况处理三点重合、三点竖直共线、三点水平共线。如果都不是就走水平主线加竖线的通用构造。有人会问三点竖直共线的情况为什么不能用通用构造其实通用构造也能用只是当 Xmin Xmax 时水平主线会退化成一条长度为 0 的线段输出一个端点相同的东西。虽然 Special Judge 很可能认但我不喜欢赌这种边界行为干脆特判掉直接输出一条从最下到最上的竖线既简洁又稳。4.2 几个必须注意的细节第一排序后取中位数时不要搞混 x 排序和 y 排序产生的下标。x 的中位数在这道题的构造里其实没有用到至少水平主线方案里不需要它。但如果你采用垂直主线方案那就反过来用 y 的中位数作为竖线位置。很多初学者会把 xs[1] 当成 ym这是典型的“看着中位数就乱取”的错误。第二竖线的输出顺序。代码里竖线的两个端点分别是 (p[i].x, p[i].y) 和 (p[i].x, ym)这两个顺序任意。点可能在 ym 上方也可能在 ym 下方Special Judge 只看线段的集合不关心端点方向。第三三个点重合时我输出 0 条线段。这可能看起来有点怪但逻辑上完全正确三个点本来就是同一个点已经是连通状态总长度为 0 就是最优。如果你不确定裁判是否接受 0 条线段的输出也可以输出一条退化的线段但没必要冒险。特判掉最安全。第四long long。线段端点坐标的绝对值可能到 1e9相减后得到跨度是 2e9勉强还没超 int但总长度累加时如果还有多条线段就可能超。而且谁也不能保证数据范围未来不会被调大所以这种题目统一用 long long 已经成了我的习惯。5. 边界数据实测从三点重合到完全共线5.1 共线数据先看水平共线三个点 (0,1)、(5,1)、(9,1)。Ymin1、Ymax1所以进入特判输出一条线段 (0,1) 到 (9,1)长度 8。这显然是最优因为三个点本来就在一条水平线上直接串起来就行根本不需要任何竖线。再看竖直共线三个点 (3,-2)、(3,4)、(3,10)。代码会输出一条竖线段 (3,-2) 到 (3,10)长度 12。三个点在一条竖直线上串起来就是最优这个也没悬念。比较容易被忽略的是斜着共线比如 (0,0)、(5,5)、(10,10)。这三个点既不是水平共线也不是竖直共线会走通用构造。y 排序是 0、5、10ym5。水平主线从 (0,5) 到 (10,5)长度 10点 (0,0) 画竖线到 (0,5)长度 5点 (10,10) 画竖线到 (10,5)长度 5。总长度 20。这里的包围盒 Xspan10、Yspan10所以下界就是 20构造达到了最优。也就是说尽管三个点在一条斜线上最优网络不是沿着斜线画一条斜段题目也不允许画斜线而是拉一条水平线再从两端各接一根竖线形成一个“匚”形长度正好是 20。5.2 重复点数据题目没有明确说三个点一定互不相同所以重复点的情况最好也测一下。假设三个点是 (0,0)、(0,0)、(10,5)。x 排序0、0、10Xmin0、Xmax10y 排序0、0、5ym0。两个特判都不触发。水平主线从 (0,0) 到 (10,0)长度 10点 (10,5) 不在 y0 上画竖线 (10,5) 到 (10,0)长度 5另外两个点已经在 y0 上不用额外画线。总长度 15正好是 Xspan10 加上 Yspan5。两个重合的点之间不需要任何线段因为它们本来就挨在一起这个方案是对的。如果三个点里有两点重合且重合点恰好不在主线上也可能走通用构造结果依然正确。比如 (0,0)、(0,0)、(4,6)y 排序 0、0、6ym0水平主线从 (0,0) 到 (4,0)点 (4,6) 画竖线到 (4,0)总长 4610等于 Xspan4 Yspan6正确。所以代码里不需要对“有一个重复点”做特殊处理只要处理好全等、全水平、全竖直这三种边界就足够了。5.3 如何自测你的输出一定合法很多选手写构造题最怕的不是思路不对而是本地看着对交上去判罚 Wrong Answer又不知道错在哪。我建议你养成写自测脚本的习惯。对于这种输出线段方案的题可以写一个暴力 checker输入三个点和你的输出然后做三件事检查每行输出是否是一条合法线段要么 x 坐标相同要么 y 坐标相同。把线段上的整数点全部加入并查集同一个线段上的点互相合并。然后检查三个给定的点是否在同一个并查集里。统计所有线段的长度和 Xspan Yspan 对比确认相等。因为坐标范围可能很大做 checker 时可以把线段离散化或者直接在数轴上用区间合并判断连通性。这个动作看起来麻烦但能帮你一次性排除大量低级错误。我每次遇到这种“输出几何方案”的题都会先拿三五个随机数据跑一遍 checker 再提交稳得多。6. 这类题背后的通用套路6.1 曼哈顿场景中中位数是常客CF1666C 不是第一个用中位数解决的曼哈顿问题也绝对不是最后一个。在曼哈顿距离下x 方向和 y 方向是解耦的很多最优化目标都可以拆开独立考虑。你要求一个点到所有点的曼哈顿距离和最小答案就是所有 x 坐标的中位数和所有 y 坐标的中位数因为一维情况下中位数最小化绝对偏差之和。本题也是一样三个点要在曼哈顿几何里连通x 方向的成本被跨度卡住y 方向的成本也被跨度卡住而中位数恰好能让你构造出一个“卡满下界”的方案。所以当你看到“曼哈顿距离”“网格路径”“水平垂直线段”这些关键词时先想想能不能把两个方向分开考虑再想想中位数在中间起什么作用。这个思路在很多题目里都能显著降低思维难度。6.2 构造题常见的“下界-构造”打法这题最值得学习的不是那个具体的构造而是“先证明下界再构造达到下界”的通用打法。很多 Codeforces 构造题都是这个套路先证明任意方案都不可能低于某个值然后给出一个恰好等于这个值的方案于是最优性不证自明。你不需要去比较无数种可能方案谁更长只需要两段话任何方案都有下界 L我的方案长度正好是 L所以我的方案最优。这种证明方式比“我试了很多种方法发现这个最短”要严谨得多也更容易写出来。这个套路在 CF 的 B、C 题里特别常见尤其是那些输出“构造任意一种方案”的题。下次看到这类题先别急着 dfs 枚举先停下来想想这个问题的答案有没有一个肉眼可见的下界如果找到了再问自己能不能画一个刚好碰到底线的形状往往答案就出来了。我个人做这类题还有一个习惯构造出来之后会再问一句“这个方案在极端数据下会不会出现退化线段”。比如坐标全相等、全共线、有重复点这些情况虽然不一定在数据里出现但想一遍能帮你写出更稳的代码。这道题我后来再看最值得记住的其实就是那一句y 坐标取中位数拉一条横线剩下的点各拉一根竖线三个点就连起来了而且连得干干净净。
CF1666C题解：曼哈顿距离下用中位数构造最优连接网络
CF1666C “Connect the Points” 是 Codeforces 上一道非常典型的构造题。题目名听着像图论实际上它考的是曼哈顿距离下的最小连接网络核心突破口就一句话三个点之间想要连通最优方案的长短其实被它们的包围盒完全锁死了。这篇文章我会从第一反应开始讲把这道题的思路、证明、代码和边界坑全部过一遍适合刚接触构造题、想练“怎么证明一个方案是最优”的选手参考。1. 看懂题目不是让你画曼哈顿最小生成树1.1 题目在说什么给平面上三个点坐标都是整数。你可以画若干条线段要求每条线段要么水平、要么垂直最终让这三个点处于同一个连通块里。注意这里说的是线段不是直线所以每条线段都有明确端点。你需要最小化所有线段的总长度然后输出一种合法方案。输出格式是先输出线段条数 k再输出 k 行每行四个整数表示一条线段的两个端点坐标。这题的坑点在于它没有限制你必须用几条线段也不限制线段之间能不能相交、能不能共享端点。你完全可以画一个很复杂的网格把三个点串起来但那样总长度会爆炸。题目要的是所有方案里总长度最小的那一类然后你随便输出其中一个就通过。坐标范围我记不清具体数值但印象中绝对值能到 1e9 这个量级所以计算总长度时用 int 有风险直接开 long long 最稳。输出端点的顺序没有要求你可以把线段的两个端点写成任意顺序Special Judge 只关心这几条线段是否合法、是否连通、总长度是否达到了理论最小值。1.2 第一反应为什么容易翻车我第一次看这题的时候脑子里跳出来的想法是这不就是求三个点在曼哈顿距离下的最小生成树吗把三个点两两之间的距离算出来跑一个 MST然后把 MST 里的每条边拆成一条水平线段和一条垂直线段画出来。这个思路看着合理实际上很容易画出一堆多余的线段。举个反例三个点分别是 (0,0)、(4,6)、(10,2)它们两两的曼哈顿距离分别是 10、8、6MST 会选择长度为 6 的边 (4,6)-(10,2) 和长度为 8 的边 (0,0)-(4,6)算一下(0,0) 到 (4,6) 是 10(4,6) 到 (10,2) 是 8(0,0) 到 (10,2) 是 10不对|0-10||0-2|12。那么 MST 边长为 8 和 10总长 18。但真实最优是 16比 MST 的结果短。问题出在曼哈顿 MST 里的每条边都走 L 形路径两条 L 形路径之间不一定能共享线段导致总长度变大。还有的人会想到直接枚举三种 L 形连接方式比如从点 A 先横后竖连到点 B再从点 B 先竖后横连到点 C。这样做得到的长度也是一个固定值但同样不一定最优因为你没有利用“三条路径可以共享同一条水平线”这个关键性质。所以这道题真正要解决的问题是能不能找到一个网络它的形状足够简单同时长度恰好等于一个谁都突破不了的下界。说白了就是“证明下界然后画一个刚好碰到下界的图形”。2. 先证下界答案被包围盒卡死了2.1 水平方向的最小花费设三个点的横坐标分别是 x1、x2、x3记录 Xmin min(x1,x2,x3)Xmax max(x1,x2,x3)。再设 Ymin、Ymax 同理。先单独看水平方向。任意一个合法的连接方案里所有水平线段加起来的长度和一定至少是 Xmax - Xmin。为什么因为最后整个图形是连通的那么横坐标最小的那个点和横坐标最大的那个点它们之间一定存在一条路径。这条路径上所有水平方向的位移绝对值加起来肯定不会小于 Xmax - Xmin。你想从横坐标 Xmin 的点出发沿着一堆水平和垂直线段走到横坐标 Xmax 的点你在水平方向上无论如何都要完成一段从 Xmin 到 Xmax 的净位移。哪怕中途来回绕路水平位移的绝对值总和只会比直线距离更大。而整个方案里的所有水平线段长度总和又一定覆盖了这条路径上的水平位移。所以所有水平线段长度之和 ≥ Xmax - Xmin。2.2 垂直方向同理长度被卡死在XspanYspan垂直方向完全对称。纵坐标最小的点和纵坐标最大的点之间一定存在路径这条路径上的垂直位移绝对值之和至少是 Ymax - Ymin所以所有垂直线段长度之和 ≥ Ymax - Ymin。把两个不等式加起来任意合法方案的总长度一定满足总长度 ≥ (Xmax - Xmin) (Ymax - Ymin)。这个下界只和三个点的包围盒有关和点在这个包围盒里的具体位置完全无关。也就是说不管三个点怎么摆只要它们围出来的横向跨度是 10、纵向跨度是 6那任何方案的线段总长度都不可能低于 16。这个结论非常强它直接告诉我们最优解不可能低于这个值。接下来只要构造出一个总长度正好等于这个下界的方案就等于找到了最优解。3. 构造方案一条水平主线加两条竖线3.1 为什么是y的中位数现在问题变成怎么画才能让水平线段总长度恰好是 Xmax - Xmin垂直线段总长度恰好是 Ymax - Ymin一个很自然的想法是先画一条水平线横跨整段 Xmin 到 Xmax长度就是 Xmax - Xmin。那么这条线应该放在哪个高度如果三个点全在这条水平线上那就一步到位了。可惜一般情况下三个点的 y 坐标各不相同不可能全落在一条水平线上。这时候就需要选一个合适的 y 值让大多数点可以通过一条竖线接到这条水平线上。如果选 y 为三个 y 坐标的中位数也就是排序后中间那个数那么三个点里至少有一个点的 y 正好等于这个中位数另外两个点一个在中位数上方、一个在中位数下方也可能有相等相等就更好。这样一来画竖线连接每个“不在水平线上的点”时每个点只需要画一条竖线。而且因为中位数把另外两个点分在了两侧这些竖线不会出现多余的重复覆盖竖线总长度刚好等于 Ymax - Ymin。你可以算一下竖线总长度等于所有 |yi - ym| 的和当 ym 是 y 的中位数时这个和恰好是 Ymax - Ymin不多不少。这就是中位数在这题里不可替代的原因。如果你取平均值三个点的 y 平均值可能在上下两个点之间但没有任何一个点正好落在这个平均值上三条线都要单独画竖线长度可能也还是 Ymax - Ymin但至少你享受不到“有一个点已经在水平线上”的便利。更关键的是平均值不保证让上下两侧的点数量均衡容易出现一条竖线被另一条竖线覆盖一部分的情况输出方案会变得奇怪。3.2 完整构造流程与手算例子具体构造分三步把三个点的 x 坐标排序得到 Xmin、Xmid、Xmax。我们暂时不关心 Xmid但后面证明会用到它。把三个点的 y 坐标排序令 ym 中间那个 y 值。先输出一条水平线段端点是 (Xmin, ym) 和 (Xmax, ym)。对每一个原始点 (xi, yi)如果 yi ≠ ym就输出一条竖直线段端点是 (xi, yi) 和 (xi, ym)。来看我之前举的例子三个点 (0,0)、(4,6)、(10,2)。x 排序后是 0、4、10所以 Xmin0、Xmax10。y 排序后是 0、2、6所以 ym2。先画水平线段 (0,2) 到 (10,2)长度 10。然后检查每个点(0,0) 不在 y2 上画竖线 (0,0) 到 (0,2)长度 2(4,6) 不在 y2 上画竖线 (4,6) 到 (4,2)长度 4(10,2) 已经在水平线上不画额外竖线。总长度 10 2 4 16正好等于 Xspan10 加上 Yspan6。从图形上看就是一条贯穿左右的水平线下面飘着一个点就拉一根竖线下来上面飘着一个点就拉一根竖线上去。因为水平线的高度选在了 y 的中位数所以下面的点和上面的点恰好各不超过一个整个图形最多只有三条线段非常干净。这个方案显然连通所有竖线都接在水平线上水平线又把所有竖线的根部连在一起所以三个点最终在一个连通块里。4. 代码实现排序、取中位、特判共线4.1 C17参考代码#include bits/stdc.h using namespace std; using ll long long; struct Point { ll x, y; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); vectorPoint p(3); for (int i 0; i 3; i) { cin p[i].x p[i].y; } vectorll xs, ys; for (int i 0; i 3; i) { xs.push_back(p[i].x); ys.push_back(p[i].y); } sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end()); ll Xmin xs[0], Xmax xs[2]; ll Ymin ys[0], Ymax ys[2]; ll ym ys[1]; // 三个点完全相同 if (Xmin Xmax Ymin Ymax) { cout 0 \n; return 0; } // 三个点竖直共线 if (Xmin Xmax) { cout 1 \n; cout Xmin Ymin Xmax Ymax \n; return 0; } // 三个点水平共线 if (Ymin Ymax) { cout 1 \n; cout Xmin Ymin Xmax Ymax \n; return 0; } vectorarrayll, 4 segs; // 水平主线 segs.push_back({Xmin, ym, Xmax, ym}); // 每个不在水平线上的点拉一条竖线到水平线 for (int i 0; i 3; i) { if (p[i].y ! ym) { segs.push_back({p[i].x, p[i].y, p[i].x, ym}); } } cout segs.size() \n; for (auto s : segs) { cout s[0] s[1] s[2] s[3] \n; } return 0; }这段代码的流程很直接先读点然后分别对 x 和 y 排序取出 Xmin、Xmax、Ymin、Ymax、ym。之后分三种特殊情况处理三点重合、三点竖直共线、三点水平共线。如果都不是就走水平主线加竖线的通用构造。有人会问三点竖直共线的情况为什么不能用通用构造其实通用构造也能用只是当 Xmin Xmax 时水平主线会退化成一条长度为 0 的线段输出一个端点相同的东西。虽然 Special Judge 很可能认但我不喜欢赌这种边界行为干脆特判掉直接输出一条从最下到最上的竖线既简洁又稳。4.2 几个必须注意的细节第一排序后取中位数时不要搞混 x 排序和 y 排序产生的下标。x 的中位数在这道题的构造里其实没有用到至少水平主线方案里不需要它。但如果你采用垂直主线方案那就反过来用 y 的中位数作为竖线位置。很多初学者会把 xs[1] 当成 ym这是典型的“看着中位数就乱取”的错误。第二竖线的输出顺序。代码里竖线的两个端点分别是 (p[i].x, p[i].y) 和 (p[i].x, ym)这两个顺序任意。点可能在 ym 上方也可能在 ym 下方Special Judge 只看线段的集合不关心端点方向。第三三个点重合时我输出 0 条线段。这可能看起来有点怪但逻辑上完全正确三个点本来就是同一个点已经是连通状态总长度为 0 就是最优。如果你不确定裁判是否接受 0 条线段的输出也可以输出一条退化的线段但没必要冒险。特判掉最安全。第四long long。线段端点坐标的绝对值可能到 1e9相减后得到跨度是 2e9勉强还没超 int但总长度累加时如果还有多条线段就可能超。而且谁也不能保证数据范围未来不会被调大所以这种题目统一用 long long 已经成了我的习惯。5. 边界数据实测从三点重合到完全共线5.1 共线数据先看水平共线三个点 (0,1)、(5,1)、(9,1)。Ymin1、Ymax1所以进入特判输出一条线段 (0,1) 到 (9,1)长度 8。这显然是最优因为三个点本来就在一条水平线上直接串起来就行根本不需要任何竖线。再看竖直共线三个点 (3,-2)、(3,4)、(3,10)。代码会输出一条竖线段 (3,-2) 到 (3,10)长度 12。三个点在一条竖直线上串起来就是最优这个也没悬念。比较容易被忽略的是斜着共线比如 (0,0)、(5,5)、(10,10)。这三个点既不是水平共线也不是竖直共线会走通用构造。y 排序是 0、5、10ym5。水平主线从 (0,5) 到 (10,5)长度 10点 (0,0) 画竖线到 (0,5)长度 5点 (10,10) 画竖线到 (10,5)长度 5。总长度 20。这里的包围盒 Xspan10、Yspan10所以下界就是 20构造达到了最优。也就是说尽管三个点在一条斜线上最优网络不是沿着斜线画一条斜段题目也不允许画斜线而是拉一条水平线再从两端各接一根竖线形成一个“匚”形长度正好是 20。5.2 重复点数据题目没有明确说三个点一定互不相同所以重复点的情况最好也测一下。假设三个点是 (0,0)、(0,0)、(10,5)。x 排序0、0、10Xmin0、Xmax10y 排序0、0、5ym0。两个特判都不触发。水平主线从 (0,0) 到 (10,0)长度 10点 (10,5) 不在 y0 上画竖线 (10,5) 到 (10,0)长度 5另外两个点已经在 y0 上不用额外画线。总长度 15正好是 Xspan10 加上 Yspan5。两个重合的点之间不需要任何线段因为它们本来就挨在一起这个方案是对的。如果三个点里有两点重合且重合点恰好不在主线上也可能走通用构造结果依然正确。比如 (0,0)、(0,0)、(4,6)y 排序 0、0、6ym0水平主线从 (0,0) 到 (4,0)点 (4,6) 画竖线到 (4,0)总长 4610等于 Xspan4 Yspan6正确。所以代码里不需要对“有一个重复点”做特殊处理只要处理好全等、全水平、全竖直这三种边界就足够了。5.3 如何自测你的输出一定合法很多选手写构造题最怕的不是思路不对而是本地看着对交上去判罚 Wrong Answer又不知道错在哪。我建议你养成写自测脚本的习惯。对于这种输出线段方案的题可以写一个暴力 checker输入三个点和你的输出然后做三件事检查每行输出是否是一条合法线段要么 x 坐标相同要么 y 坐标相同。把线段上的整数点全部加入并查集同一个线段上的点互相合并。然后检查三个给定的点是否在同一个并查集里。统计所有线段的长度和 Xspan Yspan 对比确认相等。因为坐标范围可能很大做 checker 时可以把线段离散化或者直接在数轴上用区间合并判断连通性。这个动作看起来麻烦但能帮你一次性排除大量低级错误。我每次遇到这种“输出几何方案”的题都会先拿三五个随机数据跑一遍 checker 再提交稳得多。6. 这类题背后的通用套路6.1 曼哈顿场景中中位数是常客CF1666C 不是第一个用中位数解决的曼哈顿问题也绝对不是最后一个。在曼哈顿距离下x 方向和 y 方向是解耦的很多最优化目标都可以拆开独立考虑。你要求一个点到所有点的曼哈顿距离和最小答案就是所有 x 坐标的中位数和所有 y 坐标的中位数因为一维情况下中位数最小化绝对偏差之和。本题也是一样三个点要在曼哈顿几何里连通x 方向的成本被跨度卡住y 方向的成本也被跨度卡住而中位数恰好能让你构造出一个“卡满下界”的方案。所以当你看到“曼哈顿距离”“网格路径”“水平垂直线段”这些关键词时先想想能不能把两个方向分开考虑再想想中位数在中间起什么作用。这个思路在很多题目里都能显著降低思维难度。6.2 构造题常见的“下界-构造”打法这题最值得学习的不是那个具体的构造而是“先证明下界再构造达到下界”的通用打法。很多 Codeforces 构造题都是这个套路先证明任意方案都不可能低于某个值然后给出一个恰好等于这个值的方案于是最优性不证自明。你不需要去比较无数种可能方案谁更长只需要两段话任何方案都有下界 L我的方案长度正好是 L所以我的方案最优。这种证明方式比“我试了很多种方法发现这个最短”要严谨得多也更容易写出来。这个套路在 CF 的 B、C 题里特别常见尤其是那些输出“构造任意一种方案”的题。下次看到这类题先别急着 dfs 枚举先停下来想想这个问题的答案有没有一个肉眼可见的下界如果找到了再问自己能不能画一个刚好碰到底线的形状往往答案就出来了。我个人做这类题还有一个习惯构造出来之后会再问一句“这个方案在极端数据下会不会出现退化线段”。比如坐标全相等、全共线、有重复点这些情况虽然不一定在数据里出现但想一遍能帮你写出更稳的代码。这道题我后来再看最值得记住的其实就是那一句y 坐标取中位数拉一条横线剩下的点各拉一根竖线三个点就连起来了而且连得干干净净。
