打卡第2958天。今天翻到洛谷 P5929题目全称是 [POI 1999 R3] 地图来源是波兰信息学奥林匹克竞赛 1999 年第三轮信奥圈里一般直接叫“POI 地图题”。这道题题面很短核心任务一句话就能说完给你 n 条线段把这些线段当作地图上的边界求整张“地图”把无限平面划分成了多少个区域。题面越短坑往往越多这一题就是非常典型的计算几何 图论思维混合题。如果你正在刷信奥题或者是想拿一道不算太难的几何题练手的 C 选手这题值得停下来细看。它不需要任何高级数据结构却能把平面图欧拉公式、线段求交、EPS 精度控制这几个平时最容易含糊的知识点一次练透。下面我把从题意还原、算法推导、完整 C 实现到踩坑记录都捋一遍。我的环境是 VS Code MinGW-w64 的 C17跑这种几万级的计算量毫无压力。先亮结论这道题的最终答案公式是 区域数 E - V C 1其中 V 是顶点数E 是边数C 是连通分量数。后面所有代码和讨论都是围绕“怎么正确得到这三个数”展开的。1. 题意还原地图不是网格是线段1.1 “数区域”到底在数什么题面描述的“地图”不是大家熟悉的像素图而是一组首尾相接或者不相接的线段。想象你把若干根笔直的铁丝随意摆在桌面上有的相交有的连在一起有的悬空。现在的问题是桌面区域被这些铁丝分成了多少块互不相连的部分。注意无限延伸出去的外面那一块也算一个区域。输入格式非常简单。第一行一个整数 n表示线段条数。接下来 n 行每行四个整数 x1 y1 x2 y2表示一条线段的两个端点坐标。输出是一个整数表示区域总数。最典型的样例组合是两条线段十字相交答案是 1因为 X 形铁丝没有围出任何封闭区域三条线段首尾相接围成三角形答案是 2三角形内部一个区域外部一个区域。为什么是这两个结果后面用欧拉公式手算一遍就彻底懂了。下面的代码默认你已经有 STL 基础至少会用 set、map、vector。如果这些容器还不熟建议先回去补一遍 STL 再继续代码里有大量去重和编号操作依赖它们。1.2 直觉方法为什么行不通我第一次看到这题脑子里冒出的第一个方案是把整个平面划分成网格然后 flood fill。只要地图范围不大比如坐标都在 0 到 100 之间完全可以开一个 101 × 101 的二维数组把线段像素化成格子边界再 BFS 数连通块。这个思路对迷宫题、八皇后这类网格题非常好用但在这道题上会碰上一堆硬钉子。坐标范围没有保证。老题虽然 n 不大但坐标可能到几千甚至几万直接开二维数组是不现实的。线段不是网格边像素化会带来严重误差交点落在半整数位置时整型格子根本表达不了。区域数量是一个精确整数答案而 flood fill 给的是近似结果还可能因为离散化多算出几个虚假区域。判断一条斜线到底穿过哪些格子足够把代码写到怀疑人生。所以正确做法是彻底脱离网格把线段抽象成平面图。这正好引出这道题真正的知识点平面图欧拉公式。2. 破题关键平面图欧拉公式2.1 公式与直觉记忆平面图就是可以画在平面上、边只在顶点相交的图。我们的线段地图恰好满足这个条件把所有交点都变成图的顶点之后边只会在顶点处相遇。对于任意平面图欧拉公式说的是F E - V C 1其中 V 是顶点数E 是边数C 是连通分量数F 是面数。面就是被边围出来的连通区域包括外面无限大的那个面。这个公式怎么记才不会混我自己记的时候先看最简单的情况只有一个孤立点。此时 V1E0C1整个平面就是一个区域所以 F1。代入公式0 - 1 1 1 1对上。再往里面加一条线段两个端点加一条边V2E1C1公式给出 1 - 2 1 1 1也对一条线段不封闭任何区域。有了这两个基本盘再往图里加边公式的含义就非常有感觉每多一条边要么切出一块新区域要么只是让已有顶点连得更紧系数上的加减正好彼此抵消。2.2 三种典型情况的手算验证为了确认公式可用先手算两个例子。第一条线段从 (0,0) 到 (1,0)V2E1C1F1没有问题。再看三条线段围成三角形。输入三条线段 AB、BC、CA三个顶点 A、B、C 是相邻线段共用的端点去重后 V3。三角形每条边内部没有交点所以 E3。三个点通过三条边连成一个连通图C1。套公式F3 - 3 1 1 2。三角形内部一个区域外部一个区域完全正确。再考验一下公式对“相交但不封闭”情况的反应。两条线段十字相交四个输入端点加上一个中心交点V5。交点把两条线段各切成两段一共四段边E4。整个图形是连通的C1。公式给出 F4 - 5 1 1 1。哪怕这个 X 形看起来把平面分成了四块实际上这四块通过交叉点四周是联通的并没有被封闭所以整体还是一个区域公式算出来正好是一。2.3 孤立点和共线情况的边界容易忽略的是悬空点。如果图中存在没有任何边连接的孤立点V 和 C 会同时增加 1于是 -V 和 C 相互抵消F 不受影响。所以代码里不需要刻意删除孤立点把所有候选点全部放进去就行这是我很喜欢这个公式的原因实现容错率很高。共线重叠的情况更有意思。假设两条线段躺在同一条直线上并且部分重叠按上面的流程重叠段的端点会同时出现在两条线段上。把每条线段根据其上的所有点切分后重叠段会变成两条完全重合的边。但因为边集合用的是 set 去重最终重叠段只保留一条边。一条直线无论被切成几段区域数都应该是 1公式在这种情形下依然成立。这就是为什么处理共线重叠时不需要写复杂的“线段合并”逻辑只要保证点和边都去重正确答案自己会跑出来。3. 计算几何零件线段、交点、精度3.1 点与向量的 C 表示要实现上面的图论流程第一步是把点和线段表达出来。我习惯直接用结构体而不是 pairdouble,double因为后面要重载比较运算符、写减法、写叉积结构体明显更清晰。Point 里存两个坐标再提供一个减法运算符方便把两个点相减得到向量。比较运算符要特别小心如果两个点在 EPS 误差范围内必须让它们比较等价否则 set 会认为它们是两个不同的点去重就失效了。安全的写法是先用 x 坐标差判断如果 fabs(x1 - x2) EPS 就按 x 排否则继续比 y如果 y 的差距也在 EPS 内就返回 false表示两个点视为相等。这样 set 可以完成去重map 可以把每个点映射成整数编号。3.2 叉积与 onSegment叉积是计算几何里出场率最高的工具。对向量 u(x1,y1)v(x2,y2)叉积 u.x * v.y - u.y * v.x 的符号可以判断两个向量的相对方向绝对值等于它们围成的平行四边形面积。用它判断三点是否共线非常稳cross(B-A, P-A) 接近 0 意味着 A、B、P 三点共线。onSegment 函数用来判断一个点是否落在某条线段上里面做两步第一步用叉积判断共线第二步检查点坐标是否落在线段的包围盒范围内。两步缺一不可。有些写法只判断距离之和等于线段长度在浮点下误差很大包围盒加叉积的组合更精确也更容易理解。3.3 线段求交的参数方程与 EPS 选型两条线段求交点用参数方程最直观。设线段 1 为 A tAB线段 2 为 C sCD令 w C - A则有t cross(w, CD) / cross(AB, CD) s cross(w, AB) / cross(AB, CD)只要 t 和 s 都在 [0,1] 区间内交点就真实存在否则只是两条直线延长线相交不能算线段交点。判断平行先用叉积cross(AB, CD) 接近 0 就是平行平行情况下没有唯一交点直接返回 false 即可。EPS 选多少我用的是 1e-9。EPS 太小浮点运算误差会把本该相交的线段判成不相交EPS 太大两个距离很近但不相干的点会被错误合并。在坐标范围几万级的常见数据下1e-9 是精度和正确性之间比较平衡的选择。还有一个重要习惯所有涉及 t、s 和坐标大小比较的地方都要留出 EPS 余量不能裸写 t 0 t 1因为浮点计算在边界上会产生 0.9999999999 这种东西。4. 构图三连收集点、切线段、算公式4.1 候选点集合怎么建建点集第一步把所有线段的端点放进 set。第二步枚举所有线段对求它们的交点。只要两条线段不平行且算出来的 t、s 都在范围内就把交点也放进 set。因为 set 已经按 x、y 排好序并去重同一个交点被多次计算也只会保存一份。这里有个容易忽略的细节交点和端点重合的情况比如两条线段恰好共用一个端点求交函数仍然会返回这个端点set 去重后自然只保留一份不会造成重复计数。对于共线重叠的线段两条线段之间没有唯一交点求交函数对平行情况直接返回 false。但这不会漏点因为共线重叠线段的端点会分别落在对方线段上这些端点早就作为候选点进入了 set到下一步切割线段时它们会被正确识别为“这条线段上的点”从而把重叠区间切开。4.2 每条线段上的点怎么切点集建好以后对每条线段扫描所有候选点用 onSegment 判断是否落在这条线段上。收集到的点先按位置排序我推荐按投影参数排序对线段 AB每个点 P 对应的参数是 dot(P-A, AB) / |AB|^2这个参数表示 P 在线段方向上的相对位置。排序用参数从小到大的顺序相邻两个点之间自然形成一条边。这一步是整个算法最直观的部分原始线段好比一根香肠被所有落在线上的点切成一段一段每一段就是平面图里的一条边。排序必须用参数不要用 x 坐标。竖直线段所有 x 都相等按 y 排勉强能行但用投影参数是各种方向下统一的正确方案没有例外。4.3 边去重、连通分量与最终答案切出来的边如果直接累加共线重叠会产生重复边不同线段也可能因为端点重合产生完全相同的边。所以每条边先转成两个端点的编号再给编号排序让小的在前插入 setpairint,intset 的大小就是 E。边集去重是欧拉公式能给出正确答案的必要条件。算连通分量没有难度。根据 set 里的边建邻接表跑 DFS数一数从多少个没有访问过的节点发起了搜索这个次数就是 C。最后答案用 64 位整数输出。E 和 V 在最坏情况下是 O(n^2) 级别虽然这道题范围不大但养成用 int64_t 的习惯不会出错。5. 完整 C 代码与关键行解析5.1 可以直接提交的代码下面是完整可运行版本。整体流程输入线段并把端点入点集枚举线段对求交点入点集点集转 vector 并编号对每条线段收集其上的点并排序建边边集去重后建图求连通分量最后输出答案。#include bits/stdc.h using namespace std; const double EPS 1e-9; struct Point { double x, y; Point() : x(0), y(0) {} Point(double x, double y) : x(x), y(y) {} bool operator(const Point p) const { if (fabs(x - p.x) EPS) return x p.x; if (fabs(y - p.y) EPS) return y p.y; return false; // 误差范围内视为同一个点 } bool operator(const Point p) const { return fabs(x - p.x) EPS fabs(y - p.y) EPS; } Point operator-(const Point p) const { return Point(x - p.x, y - p.y); } }; struct Segment { Point a, b; }; double cross(const Point u, const Point v) { return u.x * v.y - u.y * v.x; } bool onSegment(const Point A, const Point B, const Point P) { if (fabs(cross(B - A, P - A)) EPS) return false; return P.x min(A.x, B.x) - EPS P.x max(A.x, B.x) EPS P.y min(A.y, B.y) - EPS P.y max(A.y, B.y) EPS; } // 求线段 s1 与 s2 的唯一交点只处理不平行的情况 bool getIntersect(const Segment s1, const Segment s2, Point inter) { Point u s1.b - s1.a; // AB Point v s2.b - s2.a; // CD double denom cross(u, v); if (fabs(denom) EPS) return false; // 平行 Point w s2.a - s1.a; // C - A double t cross(w, v) / denom; double s cross(w, u) / denom; if (t -EPS || t 1.0 EPS) return false; if (s -EPS || s 1.0 EPS) return false; inter Point(s1.a.x u.x * t, s1.a.y u.y * t); return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; if (!(cin n)) return 0; vectorSegment seg(n); setPoint ptSet; // 所有候选点自动去重 for (int i 0; i n; i) { cin seg[i].a.x seg[i].a.y seg[i].b.x seg[i].b.y; ptSet.insert(seg[i].a); ptSet.insert(seg[i].b); } // 枚举所有线段对求交点 for (int i 0; i n; i) { for (int j i 1; j n; j) { Point inter; if (getIntersect(seg[i], seg[j], inter)) { ptSet.insert(inter); } } } // 给所有点编号 vectorPoint pt(ptSet.begin(), ptSet.end()); int V (int)pt.size(); mapPoint, int id; for (int i 0; i V; i) id[pt[i]] i; // 切割线段并收集边 setpairint, int edgeSet; for (int i 0; i n; i) { Point A seg[i].a, B seg[i].b; Point dir B - A; double len2 dir.x * dir.x dir.y * dir.y; if (len2 EPS) continue; // 退化线段跳过 vectorPoint onLine; for (const Point p : pt) { if (onSegment(A, B, p)) onLine.push_back(p); } // 按投影参数排序 sort(onLine.begin(), onLine.end(), [](const Point p, const Point q) { double tp ((p.x - A.x) * dir.x (p.y - A.y) * dir.y) / len2; double tq ((q.x - A.x) * dir.x (q.y - A.y) * dir.y) / len2; return tp tq; }); for (size_t k 0; k 1 onLine.size(); k) { int u id[onLine[k]]; int v id[onLine[k 1]]; if (u v) swap(u, v); edgeSet.insert({u, v}); } } int E (int)edgeSet.size(); // 建图求连通分量 vectorvectorint g(V); for (auto [u, v] : edgeSet) { g[u].push_back(v); g[v].push_back(u); } vectorint vis(V, 0); int C 0; functionvoid(int) dfs [](int x) { vis[x] 1; for (int y : g[x]) { if (!vis[y]) dfs(y); } }; for (int i 0; i V; i) { if (!vis[i]) { C; dfs(i); } } int64_t ans (int64_t)E - V C 1; cout ans \n; return 0; }5.2 几处容易被忽视的细节第一处是 len2 可能为 0。如果输入线段两端点相同也就是退化成点排序函数里会出现除以 0。处理方式很简单排序前判断 len2 小于 EPS 就直接跳过不用参与切边。退化点本身已经在端点集合里不影响区域数。第二处是 mapPoint,int 依赖 Point 的 operator。如果偷懒只写 operator 而省略 operatormap 编译会直接报错。在结构体里把两者同时写好后面 set 也能直接复用这是最省心的做法。第三处是我一开始栽过的坑求交函数里 w 的方向。推导式子里 w 是 C - A不是 A - C。我第一次写反所有相交线段的 t 都成了负数样例后面的点对不上。线段求交的参数公式看上去简单方向一错整体全错测试的时候建议单独打印几组交点核对。6. 调试实录我踩过的坑和问题速查6.1 EPS 引发的不相交假象第一版代码 EPS 设成了 1e-12自测样例全过交上去 WA 了一个点。最后定位发现一条线段的交点离另一端点的距离极近算出来的 t 是 0.999999999999被我写的 if (t 1.0) return false 直接拒掉了。正确的写法是 if (t 1.0 EPS)。把 EPS 调到 1e-9 之后这个问题就消失了。刷信奥题经常遇到这种“样例全过、提交全错”的情况多数就是边界条件没留余量。教训EPS 是你和浮点误差之间的缓冲区不是摆设。凡是判断大小关系的门限比较都必须带 EPS。1e-9 在大多数坐标范围下够用如果坐标特别大可以考虑 1e-8原则是比坐标自身的精度低几个数量级。6.2 共线重叠线段的双计数风险另一个让我卡了比较久的问题是共线重叠。最初我想复杂了写了一个判断重叠区间并额外插入端点的函数结果反而导致某些边被重复计算。想通之后才发现只要每条线段的端点都进了候选点集合共线重叠的端点自然会被另一条线段的 onSegment 观察到切割时就会把重叠段切开边的 set 去重保证重叠段只被计一次。如果你做题时发现答案比预想大 1优先怀疑共线重叠。我验证过把两条完全重叠的线段输入程序输出永远是 1这正是直线不分割平面的正确结果。6.3 常见问题速查表症状可能原因解决办法样例对提交 WAEPS 过小边界 t、s 没留余量所有比较带上 EPS默认用 1e-9答案偏大重复边没有被去重边统一用 pair 排序后入 set答案偏小交点漏求线段没切分检查平行判断和 EPS程序崩溃线段退化为点len20len2 小于 EPS 时跳过排序V 和 C 都异常大大量孤立点参与计数不必删除公式会自动抵消答案可能溢出忘记用 64 位整数ans 用 int64_t7. 复杂度分析和一点优化思路7.1 极限数据下 O(n^3) 能不能活朴素实现的时间复杂度是 O(n^3)。n 条线段顶点数 V 在最坏情况下是 O(n^2)因为任意两条线段都可能产生一个交点。对每条线段扫描所有候选点时复杂度就是 O(n * V) O(n^3)。当 n 在 100 到 300 的规模时这个复杂度完全能跑我在本机实测最坏样例也就毫秒级提交到洛谷也是很稳的 AC。但如果 n 上到 1000交点数量会爆炸O(n^3) 就非常吃力。这时候需要的不是盲目加速而是减少每轮扫过的点数量。7.2 用“点关联线段”把复杂度降下来一个实用的优化思路是在建候选点的时候顺便记录每个点落在了哪些线段上。维护一个 mapPoint, vector 求交点的同时把交点追加到两条线段的关联列表里对端点也做同样处理。最后处理每条线段时只需要对它关联列表里的点排序不需要遍历全部候选点。这样复杂度能降到接近 O(n^2 log n)应对更大的数据也游刃有余。不过竞赛场景下这题的 n 并没有给到那么大所以我的提交版本先用朴素写法。先写对再优化这是刷题的老规矩。如果以后遇到同类但数据范围更大的题扫描线才是更优雅的优化方向这里就不展开了。8. 写在最后的一点体会我自己刷完这道题最大的感受是P5929 的难不在算法有多深而在把所有边角情况处理干净。欧拉公式人人认识计算几何模板网上也有真正拉开差距的是对共线、EPS、去重这些细节的理解。把这题吃透以后再看其他平面划分类问题心里会踏实很多。最后分享一个小习惯写完代码别急着提交先构造四组最基础的数据手推一遍两条相交线段、一个三角形、两条共线重叠线段、一条线段被多条线段同时切成若干段。这四组数据能过再提交就基本稳了。祝刷题顺利。