最近在刷题时碰到一道圆上连弦计数题题号是 CF1552C Maximize the Intersections。它属于那种“看似几何、其实考贪心构造和配对顺序”的题。题目给出 2n 个点按顺时针标在圆上其中 k 条弦已经固定要求把剩余点两两连成 n-k 条新弦最后数圆内所有弦的交点目标是让这个数尽量大。当时我第一反应是暴力枚举剩余点的所有配对方式但 n 一旦到 50组合数直接炸穿。后来发现只要把未使用点按编号排序前一半顺序连后一半交点数量就能直接拉满。这篇文章就把这道题的完整思路、相交判断技巧、可以直接抄的代码以及几个我实际踩过的坑都理一遍。1. 题目到底在问什么1.1 圆上的点和弦规则并不复杂题目的场景很干净。2n 个点均匀分布在圆周上编号从 1 到 2n沿圆周顺时针依次递增。已经画好了 k 条弦每条弦连接两个不同点而且这些已有弦之间没有任何公共端点。也就是说每个点最多被一条已有弦使用。现在剩下 2n-2k 个点还没有被连线我们要做的是把它们全部两两配对画出 n-k 条新弦。因为是完美匹配所以每个未使用点最终恰好属于一条新弦不会出现某个点连了两条线的情况。最后统计的是圆内所有弦的交点总数注意是弦与弦的交点不是端点处的接触。这里的计数对象是“弦对”。由于整个方案是完美匹配任意两条弦都不可能有公共端点所以根本不用担心端点处的交点被误算。我们要做的就是在所有合法的配对方案里找一个能让交点数量达到最大值的方案然后输出这个最大值。1.2 交点数本质上是一个计数器很多人看到“圆”“弦”“交点”这几个词会先入为主当成平面几何题觉得要算距离、判断切线、求坐标之类的。实际完全不需要。关键点在于任意两条弦的端点各不相同那么这两条弦要么在圆内部相交一次要么不相交不可能出现同一对弦有好几个交点的情况。这是因为两条直线段在平面内至多相交一次。所以“总交点数”和“相交的弦对数量”是严格等价的。于是问题就被改写成了这样现在有一个包含 n 条弦的集合其中 k 条连接方式固定另外 n-k 条由我们自由选择配对问最多能让这 n 条弦里有多少对弦满足“四个端点在圆周上交替出现”。理解到这个层面之后事情就简单了只需要解决两个问题一是剩余点怎么配对二是写一个常数级的小函数判断两条弦是否相交。剩下的就是枚举所有弦对累加计数。2. 关键洞察剩余点到底应该怎么配对2.1 先想清楚要让哪些弦相交要把交点总数最大化可以先从理论上限入手。最终一共有 n 条弦任意两条弦之间最多产生 1 个交点所以答案不可能超过 C(n, 2)。但这个上限通常达不到因为有一部分弦是固定的我们只能控制新增弦的形态。可以这样拆解最终的交点数量等于三部分之和。第一部分是已有弦之间的交点这个数量由输入决定我们改不了。第二部分是新增弦和已有弦之间的交点。第三部分是新增弦和新增弦之间的交点。后面两部分受配对方案影响。其中新增弦与新增弦一共有 C(n-k, 2) 对。如果能让所有新增弦两两相交那这一部分就锁定了最大值。于是思路就变成先保证所有新增弦相互之间全部相交在满足这个条件的基础上再去争取新增弦与已有弦之间的交点。2.2 排序后“前一半顺序连后一半”的做法把未使用点收集起来按编号从小到大排成一个序列 p[0], p[1], ..., p[m-1]其中 m 2n - 2k 2(n-k)一定是个偶数。最优配对方式是p[0] 连 p[m/2]p[1] 连 p[m/2 1]……p[m/2 - 1] 连 p[m - 1]也就是把未使用点切成数量相等的两半前半部分的第 i 个点和后半部分的第 i 个点相连。注意这里不是“首尾配对”。我第一次做这道题的时候就记成了第一个连最后一个、第二个连倒数第二个结果样例能过但自己构造的数据全部偏小。这个细节是整道题的灵魂。为什么这种配对足够强假设从前半序列里取两个点 a、b并且 a 在 b 前面从后半序列里取两个对应的点 c、d并且 c 在 d 前面。因为前半序列的所有点都排在后半序列所有点的前面所以圆周上的顺序一定是 a b c d。两条新弦分别是 a-c 和 b-d。四个端点的顺序是 a、b、c、d正好交替出现。这就是两条弦在圆内相交的充要条件。由于任意两对新弦都满足这个模式新增弦之间就是两两相交的。这部分交点数量达到 C(n-k, 2)是所有配对方案里的理论峰值。2.3 为什么必须是“同序”而不是任意配对这里容易产生一个错觉既然前一半点都排在后一半点前面那是不是只要保证每条新弦的两个端点一个来自前半、一个来自后半随便怎么配都能让新增弦全部相交不是的。如果配对顺序反了比如前半的第一个点去连后本的最后一个点前半的第二个点去连后本的第一个点那么两对新弦的四个端点在圆周上的顺序就会变成“嵌套”关系而不是交替关系它们不会相交。我举个具体例子。假设 n3k12n6点 1 到 6。已有弦连接 1 和 4。那么未使用点序列是 [2,3,5,6]前半是 [2,3]后半是 [5,6]。正确配对是 2 连 5、3 连 6。逐一数交点弦 1-4 和 2-5 相交弦 1-4 和 3-6 相交弦 2-5 和 3-6 相交总交点数等于 3。如果按首尾配对写成 2 连 6、3 连 5那么弦 2-6 和 3-5 是嵌套关系不相交总交点数就只有 2。就这一步之差答案就对不上了。所以配对必须是“同序映射”前半按顺序连后半也要按顺序。从调整法的角度看任何不是同序的配对只要存在两对新弦是嵌套或分离的就可以通过交换两个端点让这两条弦变成相交而且不会破坏它们和其他弦的相交关系总交点数不降。反复调整下去最后一定会收敛到同序配对。这就是这道题最优性的直观解释。3. 圆的顺序与相交判断从几何到数组3.1 四个端点的交替法则判断两条弦是否相交不需要建坐标系不需要算圆心角更不需要画图量长度。只需要维护圆周上的编号顺序。题目给定的点本身就按顺时针从 1 到 2n 编号这提供了一个天然的一维坐标。对任意两条弦把它们的四个端点拿出来沿圆周绕一圈。如果端点顺序是“弦A的一个端点、弦B的一个端点、弦A的另一个端点、弦B的另一个端点”也就是 A、B、A、B 交替出现那么这两条弦相交。如果顺序是 A、A、B、B或者 A、B、B、A说明两条弦没有形成交叉不相交。记忆方法很简单想象两条绳子穿过一个圆四根线头从圆周上露出来。如果四根线头是交错排列的绳子在圆内部必然会碰到如果同色线头挨在一起绳子就可以各走各的互不干扰。3.2 用区间交叉来写判断代码实现时可以先把每条弦的两个端点整理成左小右大的形式 (l, r)。编号从 1 到 2n 排成环l 到 r 就是圆上一条顺时针方向的弧。两条弦相交等价于两个区间 (l1, r1) 和 (l2, r2) 在环上交叉也就是满足l1 l2 r1 r2或者l2 l1 r2 r1我第一次写判断函数的时候在这里踩了坑。如果只写一个方向比如只判断“l1 l2 r1”会漏掉另一种情况另一条弦的左端点在更左边右端点却夹在第一条弦内部。两条弦谁在“内侧”谁在“外侧”都有可能出现所以两个方向都得写。还有一个小细节这个区间模型不需要特殊处理所谓“跨过剪口”的弦。因为圆被编号成 1..2n 之后任何一条弦都能唯一表示成 (l, r) 区间这本身已经包含了它在圆周上的位置。剪开点只会影响“哪段弧叫内区间”不会改变两条弦是否相交的结论。bool isIntersect(pairint,int a, pairint,int b) { if (a.first a.second) swap(a.first, a.second); if (b.first b.second) swap(b.first, b.second); int l1 a.first, r1 a.second; int l2 b.first, r2 b.second; return (l1 l2 l2 r1 r1 r2) || (l2 l1 l1 r2 r2 r1); }这段代码里四个数理论上不会相等因为任意两条弦都没有公共端点。只要输入合法、配对正确就不会触发等号分支。如果真出现了相等情况说明前面的标记或配对逻辑写错了不是判断函数的问题。4. 完整实现步骤和核心代码4.1 数据结构设计与输入处理实现语言我用 C比较省心。先准备一个数组 used记录点是否已经被已有弦占用。再准备一个 vectorpairint,int存放所有弦。每读入一条已有弦就把两个端点标记为已使用并且把这条弦放进集合。之后把没被标记的点按编号顺序收集到一个新的 vector 里。这一步完全不需要排序因为 for 循环从 1 枚举到 2n收集顺序天然有序。#include bits/stdc.h using namespace std; bool isIntersect(pairint,int a, pairint,int b) { if (a.first a.second) swap(a.first, a.second); if (b.first b.second) swap(b.first, b.second); int l1 a.first, r1 a.second; int l2 b.first, r2 b.second; return (l1 l2 l2 r1 r1 r2) || (l2 l1 l1 r2 r2 r1); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n, k; cin n k; vectorpairint,int chords; vectorint used(2 * n 1, 0); for (int i 0; i k; i) { int x, y; cin x y; chords.push_back({x, y}); used[x] used[y] 1; } vectorint rest; for (int i 1; i 2 * n; i) { if (!used[i]) rest.push_back(i); } int half (int)rest.size() / 2; for (int i 0; i half; i) { chords.push_back({rest[i], rest[i half]}); } int ans 0; int cnt (int)chords.size(); for (int i 0; i cnt; i) { for (int j i 1; j cnt; j) { if (isIntersect(chords[i], chords[j])) { ans; } } } cout ans \n; } return 0; }4.2 构造剩余点的新弦代码里最关键的一步就是下面这一段int half (int)rest.size() / 2; for (int i 0; i half; i) { chords.push_back({rest[i], rest[i half]}); }如果 half 等于 0说明没有剩余点循环不会执行这是正确的。这时候答案就是已有弦之间的交点数程序会自动算出来。这里也顺便回答一个常见疑问为什么不需要把 rest 再排序一次因为 rest 的生成过程本身是 for 循环按编号顺序扫出来的。它天然满足递增顺序。如果你出于代码规范想再 sort 一遍也没问题只是没必要。4.3 复杂度分析和边界条件总弦数是 n其中新增弦数量是 n-k。合并之后两两枚举需要枚举 C(n, 2) 对弦。每对弦做一次 O(1) 的区间交叉判断。所以总时间复杂度是 O(n^2)空间复杂度 O(n)。常见的题目范围是 n 不超过 50也就是最多 50 条弦、1225 对弦对。哪怕有几十组测试数据这个复杂度也完全跑得动。理论上如果 n 扩大到几千这个算法依然能扛因为 O(n^2) 是稳定的。边界条件要特别关注三个第一k0也就是说一条已有弦都没有。此时 rest 包含全部 2n 个点配对后所有新增弦全部相交答案等于 C(n, 2)。第二nk也就是说未使用点数量为 0。此时 rest 为空新增弦数量为 0答案就是已有弦之间的交点数。第三输入里已有弦本身可能是相交的比如 1-4 和 2-5。这种情况必须正常计入答案。把所有弦统一放进同一个 vector 枚举自然就不会漏。5. 刷题中容易踩的坑与调试技巧5.1 配对方式记反是最大的坑正如前面说的很多人会在“前一半顺序连后一半”和“第 i 个连倒数第 i 个”之间犯迷糊。前者是让新增弦之间全部相交后者是让新增弦之间全部嵌套。一正一反答案能差出一个 C(n-k, 2) 的量级。我建议把下面这个反例记在本地测试用例里n3k1已有弦 1-4。期答案 3。错误配对 2-6、3-5 只能得到 2。正确配对 2-5、3-6 得到 3。只要本地能跑过这个用例配对方向基本就不会写错。5.2 已有弦之间的交点容易漏有些人算交点的思路是先算新增弦之间的交点再算新增弦与已有弦的交点最后把两部分相加然后忘了已有弦本身也可能相交。虽然已有弦是固定的不参与决策但它们最终也属于 n 条弦里的成员它们之间的交点当然要计入答案。最省心的做法就是像示例代码那样把所有已存在的弦和构造出来的新弦全部塞进同一个 vector然后统一双重循环。这样做天然不会漏而且思路也简单。5.3 相交判断的两个方向缺一不可相交判断的代码很容易从网上找到但很多人是背下来的不理解它为什么长这样。结果就是少写一个方向或者多写一个多余条件。正确写法需要保证两种情况都被覆盖第一种情况是第一条弦的区间“包住”了第二条弦的左端点但第二条弦的右端点伸到外面第二种情况是反过来。两个方向都满足才算相交。我见过有人只写l1 l2 l2 r1 r1 r2不写第二个方向结果遇到弦 1-4 和 2-5 能过遇到弦 2-5 和 1-4 就错了。虽然把两条弦 swap 一下也能规避但更靠谱的做法是函数内部自己处理顺序两条弦都排好序然后两个方向都判断。5.4 多组数据的初始化问题多组测试数据时used 数组很容易忘记重置。如果不清空上一组标记过的点会污染下一组导致 rest 收集出错误结果。另外chords 和 rest 这些 vector 每次都在循环内重新声明不需要手动 clear这是 C 里比较推荐的习惯。如果你为了性能在循环外声明记得在每组数据的开头 clear 一遍。5.5 用暴力对拍验证构造方案如果你对“前一半顺序连后一半”是否真的最优还有疑虑最直接的办法是写一个暴力对拍。n 比较小的时候比如 n5枚举剩余点的所有完美匹配方案取最大的交点数量再和构造方案的答案比对。我在本地随机跑了上万组数据构造方案和暴力最优解全部一致。这个结论在实践上非常稳。对拍脚本本身也很有价值它能帮你同时检查配对方向和相交判断函数是否写错。什么逻辑错误在一万组随机样例面前都会现出原形。6. 从这题能带走的通用思路6.1 配对顺序与相交性的关联这道题的核心结论是在两个点集之间建立匹配时如果两个点集都按同一顺序排列然后“同序对应相连”那么所有匹配对之间会两两相交。这个结论在很多算法题里都会出现比如圆上匹配、括号序列、区间交叠相关的构造题。遇到“有若干候选点需要两两配对并最大化交叉数或最小化交叉数”这类需求时可以先尝试把候选点按某个关键顺序排好再决定连接顺序。顺序本身就是一种很强的约束它能直接决定相交关系的开关。6.2 圆上问题的标准化处理手法把圆周上的相交问题压成一维区间交叉问题是一个非常经典的套路。以后再遇到圆上点、弦、区间覆盖之类的题目不妨先想清楚能不能把“环”拆成“线性数组”再用区间和排序去解决。拆环的方式不唯一关键是让所有关系都能在一个方向上表达清楚。这道题还有一点很值得学习它暴露了“首尾配对”和“顺序配对”在相交性上的巨大差异。很多构造题都藏着一个类似的心理陷阱——靠直觉选一个看起来很自然的配对方式结果恰恰是最差的。动手之前先在小样例上验证直觉能省下大量调试时间。最后再分享一个小技巧做这类题别急着写代码。先在草稿纸上画几个小圆把点编号标上自己手算几组答案再开始写。CF1552C 的结论虽然简单但不亲手画一画四个端点的交替顺序很容易在配对方向上翻车。这个习惯帮我避开了很多构造题的大坑。