第 7 章 · 01 计算几何（对应 docs/geometry/）

第 7 章 · 01 计算几何（对应 docs/geometry/）

本节定位：对应 OI Wiki docs/geometry/（共 14 篇）。难度：高阶（省选/IOI）。前置依赖：第 6 章数学（向量、行列式）、基本 C++（结构体、浮点运算）。本节是非难点导读节，把几何算法按"基础工具 → 经典算法"串起来，凸包是必会核心，精度处理是最大坑。

⚠️ 注意：计算几何代码量大、细节多、精度是头号杀手。本节只导航，具体实现回 docs/geometry/ 各页。建议每个算法都先在纸上画图再写代码。

知识地图

一、基础工具：向量运算（docs/geometry/Vector.md 等）

几何题的"螺丝刀"，所有后续算法都建立其上。把点用 struct {double x,y;} 表示，重载运算符。

• 点积（dot）：a·b = a.x*b.x + a.y*b.y = |a||b|cosθ，判断垂直（=0）、夹角锐（>0）钝（<0）、求长度平方、投影。
• 叉积（cross）：a×b = a.x*b.y - a.y*b.x = |a||b|sinθ，判断方向（正/负/零 = c 在 ab 左侧/右侧/共线）、求三角形有向面积（= cross/2）、求凸包的核心、判断线段相交。
• 常用函数：len(a) 长度、dist(a,b) 距离、angle(a,b) 夹角、rotate(a,θ) 旋转。把点当向量，用 +、-、点积、叉积四个运算，几乎能表达所有几何关系。

💡 学习提示：叉积的符号判定（cross(b-a, c-a) > 0 表示 c 在 ab 左侧）是计算几何的"万能判据"。凸包、半平面交、判断线段相交都用它，务必形成条件反射。线段相交的"快速排斥 + 跨立实验"本质就是两次叉积判方向。

二、浮点精度陷阱（贯穿全章）

• 用 eps = 1e-9 作为容差，判断相等用 fabs(x) < eps 而非 x == 0。
• 比较大小用 x > y + eps（大于）、x > y - eps（大于等于），输出坐标记得控制精度。
• 避免除以接近 0 的数（用叉积判平行而非直接除斜率），注意共线退化情况（凸包三点共线、半平面交平行边）。
• 尽量用整数坐标（若题目允许）避免精度问题；必须用浮点时全程保持 double，不要中途转 int。

⚠️ 注意：精度问题是计算几何题 WA 的第一大原因。写代码时全程用 eps 容差比较，不要直接 ==。常见做法是封装一个 int sgn(double x){return x<-eps?-1:x>eps;} 函数返回 -1/0/1，所有比较走 sgn。

三、凸包（docs/geometry/convex-hull.md）—— 必会

求包围所有点的最小凸多边形。所有几何题的"基础设施"。

• Graham 扫描：O(n log n)，先按极角排序，再用栈维护凸性，叉积判转向——栈顶两点与新点构成"右转"则弹栈。
• Andrew 单调链（更推荐）：按 x（x 相同按 y）坐标排序，分别从左到右求下凸壳、从右到左求上凸壳，代码比 Graham 简洁，不易写错。复杂度 O(n log n)（排序是瓶颈）。

四、旋转卡壳（docs/geometry/rotating-calipers.md）

在凸包上用两条平行线"夹"住多边形，找对踵点（antipodal points，平行线碰到的一对点）。典型应用：求最远点对距离（即点集直径，平面最大距离），O(n)。关键是随着一条边旋转，对踵点也单调移动，不需要回退。也可求凸包最小覆盖矩形、最小宽度。

五、半平面交（docs/geometry/half-plane.md）

每个半平面是一条有向直线的一侧（用直线起点终点表示"左侧"），求多个半平面的交集（结果为凸多边形，可能为空）。用排序（按极角）+ 双端队列维护，类似凸包但维护的是直线。O(n log n)。典型应用：多边形交、多边形核（看多边形内哪个区域能看到所有边）、线性规划可行域。

六、扫描线（docs/geometry/scanning.md）

把二维问题降成一维：用一条扫描线扫过平面，在关键事件点（线段端点、矩形上下边）更新数据结构（常用线段树或平衡树）。典型应用：矩形面积并（把矩形拆成上下边，按 y 排序，扫描时线段树维护 x 方向有效长度）、求线段交点（按 x 排序，平衡树维护 y 顺序）。

七、最近点对（docs/geometry/nearest-points.md）

平面上 n 个点中距离最近的两点。朴素 O(n²)，分治到 O(n log n)：按 x 排序，分左右两半递归求最小值 d，合并时只检查"跨中线、横向宽度为 2d"的带状区域，对该区域按 y 排序后每个点只检查常数个邻居。归并排序式的实现能稳定 O(n log n)。

各算法的考查频率

💡 学习提示：几何题代码量大，建议把"点/向量结构体 + 基本运算 + sgn 容差"整理成自己的模板，比赛时直接复制。凸包和旋转卡壳的代码也建议模板化。模板能在比赛中省下大量调试时间。

学习建议

1. 必会清单：向量运算（点积/叉积）、凸包（优先 Andrew 单调链）、eps 精度处理。这三个是几何题的地基，不会就无法做任何几何题。
2. 精度第一：任何几何题，先把 eps、sgn、带容差的比较函数写好，再写算法主体。90% 的 WA 出在精度。
3. 画图习惯：几何算法必须在纸上画图，尤其凸包的栈维护、半平面交的双端队列。纯读代码几乎不可能懂。
4. 读 Wiki 顺序：Vector.md（向量）→ convex-hull.md（凸包）→ rotating-calipers.md（旋转卡壳）→ half-plane.md（半平面交）→ scanning.md（扫描线）→ nearest-points.md（最近点对）。
5. 代码模板化：几何题代码长，建议把点/向量结构体、基本运算、sgn 函数整理成自己的模板，比赛时直接套。

💡 学习提示：计算几何是"理解容易、实现难"的典型。凸包思路一句话能说清，但叉积判转向、排序、栈维护的细节极多。建议凸包模板亲手敲 3 遍以上，形成肌肉记忆。

本节要点

• 向量运算是地基：点积判垂直/夹角，叉积判方向/面积/凸性。
• 浮点精度 eps = 1e-9 是头号坑，全程用 sgn 容差比较，不要 ==。
• 凸包必会：Andrew 单调链比 Graham 简洁，优先学。
• 旋转卡壳求最远点对、半平面交求多边形交、扫描线求面积并、分治求最近点对。
• 几何题代码长细节多，务必画图 + 模板化；深入见 docs/geometry/ 各页。