企业官网建设流程全解析

打卡第2958天。今天翻到洛谷 P5929，题目全称是 [POI 1999 R3] 地图，来源是波兰信息学奥林匹克竞赛 1999 年第三轮，信奥圈里一般直接叫“POI 地图题”。这道题题面很短，核心任务一句话就能说完：给你 n 条线段，把这些线段当作地图上的边界，求整张“地图”把无限平面划分成了多少个区域。题面越短，坑往往越多，这一题就是非常典型的计算几何 + 图论思维混合题。

如果你正在刷信奥题，或者是想拿一道不算太难的几何题练手的 C++ 选手，这题值得停下来细看。它不需要任何高级数据结构，却能把平面图欧拉公式、线段求交、EPS 精度控制这几个平时最容易含糊的知识点一次练透。下面我把从题意还原、算法推导、完整 C++ 实现到踩坑记录都捋一遍。我的环境是 VS Code + MinGW-w64 的 C++17，跑这种几万级的计算量毫无压力。

先亮结论：这道题的最终答案公式是 区域数 = 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 是面数。面就是被边围出来的连通区域，包括外面无限大的那个面。

这个公式怎么记才不会混？我自己记的时候先看最简单的情况：只有一个孤立点。此时 V=1，E=0，C=1，整个平面就是一个区域，所以 F=1。代入公式：0 - 1 + 1 + 1 = 1，对上。再往里面加一条线段：两个端点加一条边，V=2，E=1，C=1，公式给出 1 - 2 + 1 + 1 = 1，也对，一条线段不封闭任何区域。有了这两个基本盘，再往图里加边，公式的含义就非常有感觉：每多一条边，要么切出一块新区域，要么只是让已有顶点连得更紧，系数上的加减正好彼此抵消。

2.2 三种典型情况的手算验证

为了确认公式可用，先手算两个例子。第一条线段从 (0,0) 到 (1,0)，V=2，E=1，C=1，F=1，没有问题。

再看三条线段围成三角形。输入三条线段 AB、BC、CA，三个顶点 A、B、C 是相邻线段共用的端点，去重后 V=3。三角形每条边内部没有交点，所以 E=3。三个点通过三条边连成一个连通图，C=1。套公式：F=3 - 3 + 1 + 1 = 2。三角形内部一个区域，外部一个区域，完全正确。

再考验一下公式对“相交但不封闭”情况的反应。两条线段十字相交，四个输入端点加上一个中心交点，V=5。交点把两条线段各切成两段，一共四段边，E=4。整个图形是连通的，C=1。公式给出 F=4 - 5 + 1 + 1 = 1。哪怕这个 X 形看起来把平面分成了四块，实际上这四块通过交叉点四周是联通的，并没有被封闭，所以整体还是一个区域，公式算出来正好是一。

2.3 孤立点和共线情况的边界

容易忽略的是悬空点。如果图中存在没有任何边连接的孤立点，V 和 C 会同时增加 1，于是 -V 和 +C 相互抵消，F 不受影响。所以代码里不需要刻意删除孤立点，把所有候选点全部放进去就行，这是我很喜欢这个公式的原因：实现容错率很高。

共线重叠的情况更有意思。假设两条线段躺在同一条直线上并且部分重叠，按上面的流程，重叠段的端点会同时出现在两条线段上。把每条线段根据其上的所有点切分后，重叠段会变成两条完全重合的边。但因为边集合用的是 set 去重，最终重叠段只保留一条边。一条直线无论被切成几段，区域数都应该是 1，公式在这种情形下依然成立。这就是为什么处理共线重叠时不需要写复杂的“线段合并”逻辑，只要保证点和边都去重，正确答案自己会跑出来。

3. 计算几何零件：线段、交点、精度

3.1 点与向量的 C++ 表示

要实现上面的图论流程，第一步是把点和线段表达出来。我习惯直接用结构体，而不是 pair<double,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 边去重、连通分量与最终答案

切出来的边如果直接累加，共线重叠会产生重复边，不同线段也可能因为端点重合产生完全相同的边。所以每条边先转成两个端点的编号，再给编号排序让小的在前，插入 set<pair<int,int>>，set 的大小就是 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; vector<Segment> seg(n); set<Point> 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); } } } // 给所有点编号 vector<Point> pt(ptSet.begin(), ptSet.end()); int V = (int)pt.size(); map<Point, int> id; for (int i = 0; i < V; i++) id[pt[i]] = i; // 切割线段并收集边 set<pair<int, 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; // 退化线段，跳过 vector<Point> 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(); // 建图求连通分量 vector<vector<int>> g(V); for (auto [u, v] : edgeSet) { g[u].push_back(v); g[v].push_back(u); } vector<int> vis(V, 0); int C = 0; function<void(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 就直接跳过，不用参与切边。退化点本身已经在端点集合里，不影响区域数。

第二处是 map<Point,int> 依赖 Point 的 operator<。如果偷懒只写 operator== 而省略 operator<，map 编译会直接报错。在结构体里把两者同时写好，后面 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 常见问题速查表

7. 复杂度分析和一点优化思路

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 用“点关联线段”把复杂度降下来

一个实用的优化思路是：在建候选点的时候，顺便记录每个点落在了哪些线段上。维护一个 map<Point, vector >，求交点的同时把交点追加到两条线段的关联列表里；对端点也做同样处理。最后处理每条线段时，只需要对它关联列表里的点排序，不需要遍历全部候选点。这样复杂度能降到接近 O(n^2 log n)，应对更大的数据也游刃有余。

不过竞赛场景下这题的 n 并没有给到那么大，所以我的提交版本先用朴素写法。先写对，再优化，这是刷题的老规矩。如果以后遇到同类但数据范围更大的题，扫描线才是更优雅的优化方向，这里就不展开了。

8. 写在最后的一点体会

我自己刷完这道题最大的感受是：P5929 的难，不在算法有多深，而在把所有边角情况处理干净。欧拉公式人人认识，计算几何模板网上也有，真正拉开差距的是对共线、EPS、去重这些细节的理解。把这题吃透以后，再看其他平面划分类问题，心里会踏实很多。

最后分享一个小习惯：写完代码别急着提交，先构造四组最基础的数据手推一遍：两条相交线段、一个三角形、两条共线重叠线段、一条线段被多条线段同时切成若干段。这四组数据能过，再提交就基本稳了。祝刷题顺利。