第 110 章 计算几何入门¶
配套例题：BISHI86 圆覆盖、BISHI15 小红的夹吃棋 来源：S3 day9《在数学花园里闲逛》第 50–59 页（平面直角坐标系 / 直线的三种表示 / 点到点距离公式 / 点到直线距离公式 / 圆） 前置：23-浮点与科学计数法、44-二分
110.0 这一章为什么存在¶
S3 day9 的《在数学花园里闲逛》最后十页专门讲了一套平面几何工具： 平面直角坐标系、直线的一般式 / 点斜式 / 截距式、点到点距离公式、点到直线距离公式、圆。 这是课件里唯一系统讲几何的地方，但牛客的 147 道笔试题里没有一道纯计算几何题。
原因不难理解：笔试题偏向「模板 + 数据结构 + DP」，计算几何在企业笔试里出现率极低。 但它在两类场景下会突然冒出来：
| 场景 | 例子 |
|---|---|
| 题面里出现坐标 | 「平面上 \(n\) 个点」「以原点为圆心的圆」——BISHI86 就是 |
| 需要判断「顺时针 / 逆时针 / 共线」 | 凸包、面积、判断点在多边形内 |
| 网格棋盘的方向判断 | BISHI15 的「横向 / 纵向三连」本质是方向向量 |
这一章的目标不是把凸包、半平面交、最小圆覆盖都讲一遍（那是省选内容），
而是把 day9 课件里那几个公式变成 Python 里可以直接抄的工具，
并说清楚一个 Python 独有的机会与陷阱：用 complex 当二维向量。
110.1 平面直角坐标系与 Python 的 complex¶
课件的起点是「一个点用有序数对 \((x, y)\) 表示」。在 Python 里有三种选择：
| 表示 | 写法 | 距离 | 加减 | 精度 |
|---|---|---|---|---|
| 两个变量 | x, y |
手写 | 手写 | 看类型 |
| 元组 | (x, y) |
手写 | 手写 | 整数可精确 |
| 复数 | complex(x, y) |
abs(p - q) |
p + q |
⚠️ 永远是 float |
complex 是 Python 相对 C++ 的一个真实优势：内置的二维向量类型，运算符全都重载好了。
# [片段]
p = complex(3, 4) # 点 (3, 4)，也可以写成 3 + 4j
q = 1 + 2j # 虚部后缀是 j 不是 i，这是 Python 的写法
p.real # 3.0 横坐标
p.imag # 4.0 纵坐标
p + q # (4+6j) 向量加
p - q # (2+2j) 向量减（q 指向 p 的向量）
p * 2 # (6+8j) 数乘
abs(p) # 5.0 模长 = 到原点的距离
abs(p - q) # 到 q 的距离
p * 1j # (-4+3j) ★ 逆时针旋转 90°
p * (-1j) # ( 4-3j) ★ 顺时针旋转 90°
p * 1j就是逆时针转 90°，因为 \(i \cdot (x + yi) = -y + xi\)， 恰好是把 \((x, y)\) 变成 \((-y, x)\)。任意角度旋转则是乘以 \(\cos\theta + i\sin\theta\)，用cmath.exp(1j * theta)得到。 这一条能省掉几十行三角函数代码。
读入一批点：
# [片段]
import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
# 每个点占两个 token，第 i 个点的 x 在下标 1+2i、y 在 2+2i
pts = [complex(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)]
110.2 点积与叉积：几何题的两把钥匙¶
设向量 \(\vec{a} = (x_1, y_1)\)、\(\vec{b} = (x_2, y_2)\)：
| 量 | 符号含义 | 用途 |
|---|---|---|
| 点积 \(> 0\) | 夹角 \(< 90°\) | 判断「同向 / 反向」、投影长度 |
| 点积 \(= 0\) | 垂直 | 判垂直 |
| 叉积 \(> 0\) | \(\vec b\) 在 \(\vec a\) 逆时针方向 | 判左右转、判凸凹 |
| 叉积 \(= 0\) | 共线 | 判三点共线 |
| 叉积绝对值 | 平行四边形面积 | 三角形面积 = 一半 |
叉积的几何含义，一句话：站在 \(\vec a\) 上朝它指的方向看， \(\vec b\) 偏在左边就是正，偏在右边就是负，在同一条直线上就是零。 公式里的 \(\sin\theta\) 正是「偏了多少」——转角超过 \(180°\) 时 \(\sin\) 变号， 符号也就跟着翻过来，与「左 / 右」的直觉严丝合缝。
所以「\(o \to a \to b\) 是左转还是右转」这个几何问题， 被压成了一次减法和两次乘法的符号判断。凸包、多边形面积、线段相交、 点在多边形内，全都建立在这一个符号上。
用 complex 一行算出来¶
复数乘法 \(\bar{a} \cdot b = (x_1 - y_1 i)(x_2 + y_2 i) = (x_1x_2 + y_1y_2) + (x_1y_2 - x_2y_1)i\)。
实部恰好是点积，虚部恰好是叉积。
# [片段]
def dot(o, a, b):
"""向量 oa 与 ob 的点积。"""
# 先减去 o，把两个点变成以 o 为起点的向量；取共轭后相乘，实部即点积
return ((a - o).conjugate() * (b - o)).real
def cross(o, a, b):
"""向量 oa 与 ob 的叉积。> 0 表示 o->a->b 是逆时针（左转）。"""
# 同一次复数乘法的虚部就是叉积，点积叉积一起算，省一半运算
return ((a - o).conjugate() * (b - o)).imag
conjugate()不能省。忘记取共轭得到的是 \((x_1x_2 - y_1y_2) + (x_1y_2 + x_2y_1)i\)，两个分量都不对。 记忆方法：共轭相当于把第一个向量「翻转角度」，乘完之后角度就是夹角。
整数版（大坐标时必须用）¶
# [片段]
def cross_i(ox, oy, ax, ay, bx, by):
"""整数叉积：完全精确，坐标可以到 1e18。"""
# 展开式就是 (oa 的 x)*(ob 的 y) - (ob 的 x)*(oa 的 y)
# 全程只有整数加减乘，Python 大整数自动扩位，没有任何舍入
return (ax - ox) * (by - oy) - (bx - ox) * (ay - oy)
⚠️ 这是本章最重要的陷阱：
complex的实部虚部是 IEEE 754 双精度， 只有 53 位有效尾数，能精确表示的整数上界是 \(2^{53} \approx 9\times10^{15}\)。 题目给 \(|x|, |y| \le 10^9\) 时，叉积能到 \(4\times10^{18}\) —— 远远超出， 结果会带上几百的误差，判「叉积是否为 0」直接错。规则： - 坐标 \(\le 10^7\)、只求距离和面积 → 用
complex，方便； - 坐标 \(\ge 10^8\)，或需要精确判断共线 / 左右→ 必须用整数元组 +cross_i。Python 的整数是无限精度，这里反而比 C++ 的
long long更安全。
为什么换成整数就没有精度问题：叉积只用到减法与乘法， 而整数的加减乘结果仍是整数，Python 会按需扩展位数，一位都不会丢。 浮点则不然——每次运算都要把结果塞回 53 位尾数，塞不下就四舍五入。 判断「叉积是否等于 0」时，这点舍入是致命的： 真正共线的三点算出 \(10^{-7}\)、真正不共线的算出 \(0\)，两种错误都会发生， 而这类判断的结果是离散的（左 / 右 / 共线），一步错，整条凸包就错。
判据：结果只用来比较符号或判等于零 \(\Rightarrow\) 必须整数； 结果只是要输出一个近似值 \(\Rightarrow\) 浮点无妨。
110.3 直线的三种表示¶
课件给了三种（第 54–56 页）：
| 名称 | 形式 | 优点 | 缺点 |
|---|---|---|---|
| 一般式 | \(Ax + By + C = 0\) | 能表示所有直线（含竖直线） | 系数不唯一（可整体缩放） |
| 点斜式 | \(y - y_0 = k(x - x_0)\) | 直观 | 竖直线 \(k\) 不存在 |
| 截距式 | \(\dfrac{x}{a} + \dfrac{y}{b} = 1\) | 直观 | 过原点、平行坐标轴时失效 |
竞赛里只用一般式，另外两种在退化情况下会崩。
从两点求一般式¶
过 \(P_1(x_1, y_1)\)、\(P_2(x_2, y_2)\) 的直线：
# [片段]
def line_from(x1, y1, x2, y2):
"""两点式 -> 一般式 Ax + By + C = 0。整数输入则系数全是整数，精确无误差。"""
A = y2 - y1 # (A, B) 恰是直线的法向量，(-B, A) 是方向向量
B = x1 - x2 # 竖直线只是 B == 0，没有任何需要特判的地方
C = -(A * x1 + B * y1) # 把 P1 代回方程解出 C，保证 P1 在直线上
return A, B, C
为什么不用斜率：\(k = \frac{y_2 - y_1}{x_2 - x_1}\) 在 \(x_1 = x_2\) 时除零。 一般式的 \((A, B)\) 恰好是法向量，\((-B, A)\) 是方向向量， 竖直线只是 \(B = 0\)，毫无特殊之处。
110.4 距离公式¶
点到点（课件第 57 页）¶
# [片段]
abs(p - q) # complex 写法
math.dist((x1, y1), (x2, y2)) # Python 3.8+ 内置，C 层实现
math.hypot(x1 - x2, y1 - y2) # 同上，且防溢出
能不开根就不开根。比较距离大小时直接比距离平方（整数运算，零误差）：
(x1-x2)**2 + (y1-y2)**2。BISHI86 就是靠这一条把浮点误差彻底消灭的。
点到直线（课件第 58 页）¶
# [片段]
from math import hypot
def point_line_dist(x0, y0, A, B, C):
"""点 (x0,y0) 到直线 Ax+By+C=0 的距离。"""
# 分子是点代入方程的绝对值，分母 hypot(A,B) 是法向量长度，用于归一化
return abs(A * x0 + B * y0 + C) / hypot(A, B)
叉积视角：点 \(P\) 到直线 \(P_1P_2\) 的距离 \(= \dfrac{|\vec{P_1P} \times \vec{P_1P_2}|}{|P_1P_2|}\) ——分子是平行四边形面积，分母是底，商就是高。两个公式完全等价。
点到线段的距离（比直线更常考）¶
线段有端点，垂足可能落在线段外：
# [片段]
def point_seg_dist(p, a, b):
"""点 p 到线段 ab 的距离。p, a, b 都是 complex。"""
if a == b:
return abs(p - a) # 线段退化成一个点，直接算点到点
t = ((p - a).conjugate() * (b - a)).real / abs(b - a) ** 2 # 投影参数
# t 是垂足在 ab 上的比例：0 在 a、1 在 b
if t < 0:
return abs(p - a) # 垂足在 a 外侧
if t > 1:
return abs(p - b) # 垂足在 b 外侧
return abs(p - (a + t * (b - a))) # 垂足在段内
忘记 clamp
t到 \([0,1]\) 是点到线段距离的第一大 bug。
110.5 判左右转与三点共线¶
# [片段]
c = cross_i(ox, oy, ax, ay, bx, by)
# 只看 c 的符号，不看它的大小；整数运算保证符号绝对可信
# c > 0 : o->a->b 逆时针（左转）
# c < 0 : o->a->b 顺时针（右转）
# c == 0: 三点共线
| 想判断的事 | 用什么 |
|---|---|
| 三点共线 | 叉积 \(=0\) |
| 点在直线哪一侧 | 叉积的符号 |
| 两线段是否相交 | 两次「跨立实验」：各自的两个端点在对方两侧 |
| 多边形是凸的吗 | 相邻三点叉积符号全同 |
| 凸包（Andrew 单调链） | 排序后维护叉积符号 |
跨立实验：线段相交判定¶
# [片段]
def seg_intersect(p1, p2, p3, p4):
"""判断线段 p1p2 与 p3p4 是否相交（不含端点重合等退化情况的细分）。"""
d1 = cross(p3, p4, p1) # p1 在直线 p3p4 的哪一侧
d2 = cross(p3, p4, p2) # p2 在哪一侧
d3 = cross(p1, p2, p3) # 反过来再判一次
d4 = cross(p1, p2, p4)
# 乘积为负 = 两个端点分居直线两侧；两条线段互相跨立才算相交
return (d1 * d2 < 0) and (d3 * d4 < 0) # 严格跨立
退化情况（共线、端点落在另一条线段上）要单独讨论， 判定条件是「叉积为 0 且投影落在区间内」。 竞赛里如果题面保证「没有三点共线」，可以直接用严格跨立。
110.6 多边形面积：鞋带公式¶
对顶点依次为 \(P_1, P_2, \dots, P_n\) 的简单多边形：
# [片段]
def polygon_area2(pts):
"""返回**两倍**面积的有符号值（整数坐标 -> 整数结果，零误差）。
正数表示顶点是逆时针给出的，负数表示顺时针。
真实面积 = abs(结果) / 2。
"""
s = 0
n = len(pts)
for i in range(n):
x1, y1 = pts[i]
x2, y2 = pts[(i + 1) % n] # 取模让最后一条边回到起点，闭合多边形
s += x1 * y2 - x2 * y1 # 每项是「原点、Pi、Pi+1」三角形的两倍有符号面积
return s # 凹的部分贡献负值，正负抵消后恰好是多边形面积
返回两倍面积而不是面积本身，是计算几何的标准技巧： 整数坐标下两倍面积一定是整数，避免了
/2引入的.5浮点。 需要判「面积是否为整数」「面积大小比较」时全程用两倍值。
皮克定理（格点多边形，偶尔考）：\(S = I + \dfrac{B}{2} - 1\)， 其中 \(I\) 是内部格点数、\(B\) 是边界格点数。边 \((x_1,y_1)\to(x_2,y_2)\) 上的格点数是 \(\gcd(|x_2-x_1|, |y_2-y_1|)\)。
110.7 圆¶
课件第 59 页只给了圆的方程：\((x-a)^2 + (y-b)^2 = r^2\)。竞赛里最常用的是覆盖判定：
| 判定 | 条件（全用平方，不开根） |
|---|---|
| 点 \((x,y)\) 在以原点为心、半径 \(r\) 的圆内（含边界） | \(x^2 + y^2 \le r^2\) |
| 点在圆 \((a,b,r)\) 内 | \((x-a)^2 + (y-b)^2 \le r^2\) |
| 两圆相离 | \(d^2 > (r_1+r_2)^2\) |
| 两圆内含 | \(d^2 < (r_1-r_2)^2\) |
| 两圆相交 | 上面两个都不成立 |
「不开根」是圆类题目的通用铁律。 题面给的 \(r\) 若是整数，全程整数比较；若答案要求输出 \(r\)， 只在最后一步开一次根号。BISHI86 正是这个套路。
最小覆盖半径的单调性¶
「半径 \(r\) 越大 → 被覆盖的点越多 → 覆盖权值和单调不减」， 所以求「最小的 \(r\) 使权值和 \(\ge S\)」是一个答案单调问题：
- 做法一：实数二分 \(r\)，每次 \(O(n)\) 数点 → \(O(n\log\frac{1}{\varepsilon})\)，慢且有精度问题；
- 做法二（正确做法）：最优半径一定恰好等于某个点到圆心的距离 （再小就丢掉那个点，再大是浪费）。所以按距离平方排序 + 前缀和，\(O(n\log n)\)， 而且全程整数。
这个「答案一定落在某个候选值上」的观察，比二分更值钱—— 它把实数问题降成了离散问题。见 44-二分。
110.8 精度：什么时候能用浮点¶
| 情形 | 建议 |
|---|---|
| 只比较大小 | 整数平方，绝不开根 |
| 需要输出距离 / 面积 | 最后一步开根，输出 6 位小数 |
| 判共线 / 左右 / 相交 | 必须整数叉积 |
| 坐标本身是小数 | 设 EPS = 1e-9，用 abs(x) < EPS 代替 x == 0 |
| 坐标 \(\le 10^9\) | complex 会丢精度，改整数元组 |
# [片段]
EPS = 1e-9 # 比这个还小的量一律视为 0
def sgn(x):
"""浮点符号函数：-1 / 0 / 1。所有浮点比较都应该经过它。"""
if x > EPS:
return 1
if x < -EPS:
return -1
return 0 # 落在 (-EPS, EPS) 里就当成 0，吸收累积误差
EPS取多少？经验值：坐标绝对值 \(\le 10^6\) 时取1e-9； 坐标更大时要相应放大到1e-6，因为双精度的绝对误差随数值增大而增大。 详见 23-浮点与科学计数法。
110.9 可行规模判断¶
| 任务 | 复杂度 | Python 可行的 \(n\) |
|---|---|---|
| 读入 + 距离平方排序 | \(O(n\log n)\)，排序在 C 层 | \(n \le 3\times10^5\) ✅ |
| 逐点算叉积（纯 Python 循环） | \(O(n)\) | \(n \le 2\times10^6\) ✅ |
| 凸包（Andrew 单调链） | \(O(n\log n)\)，但栈操作在 Python 层 | \(n \le 2\times10^5\) ⚠️ |
| 枚举点对（最近点对暴力） | \(O(n^2)\) | \(n \le 3000\) ⚠️ |
| 分治最近点对 | \(O(n\log^2 n)\) | \(n \le 10^5\) ⚠️ 常数很大 |
| 旋转卡壳 | \(O(n)\)（凸包之后） | 同凸包 |
结论：计算几何在 Python 下的可行性完全取决于「有多少工作能交给 sort」。
排序 + 前缀和类的题（比如 BISHI86）毫无压力；
需要在 Python 层做 \(10^6\) 次叉积的题就要小心了。
110.10 例题¶
BISHI86 圆覆盖（中等）¶
平面上 \(n \le 10^5\) 个点，第 \(i\) 个点坐标 \((x_i, y_i)\)（\(|x_i|,|y_i| \le 10^9\)）、权值 \(v_i < 2^{31}\)。 以原点为圆心放一个圆，被覆盖的点满足 \(x_i^2+y_i^2 \le r^2\)。 求使覆盖权值和 \(\ge S\)（\(S \le 10^{14}\)）的最小半径 \(r\)，无解输出 \(-1\)。 相对误差 \(10^{-6}\) 内算对。时限：C/C++ 3 秒，其他语言 6 秒。 题面见 BISHI86 原题（牛客）。
ℹ️
solutions/BISHI86.py已存在，下面的代码与它一致，并由scripts/verify_docs.py用官方样例实测通过。
三个观察串起整题：
- 覆盖判定用 \(x^2+y^2 \le r^2\)，两边都是平方 → 全程不开根；
- 权值和随 \(r\) 单调不减 → 答案单调；
- 最优 \(r\) 必然等于某个点的距离，所以按 \(d^2 = x^2+y^2\) 排序后 找第一个使前缀和 \(\ge S\) 的点，答案就是 \(\sqrt{d^2}\)。
import sys
from math import sqrt
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); S = int(data[1])
pts = []
p = 2 # 前两个 token 是 n 和 S
for _ in range(n):
x = int(data[p]); y = int(data[p + 1]); v = int(data[p + 2]); p += 3
pts.append((x * x + y * y, v)) # ★ 用距离平方排序，整数无精度损失
pts.sort() # 元组按第一项排，即按到原点的距离由近及远
acc = 0 # 半径扫过这些点时累计到的权值
for d2, v in pts:
acc += v
if acc >= S: # 第一个达标的点，其距离就是最小半径
# 半径只要再小一点就会丢掉这个点，权值和不够；所以它是下确界且能取到
sys.stdout.write("%.6f\n" % sqrt(d2)) # 全程唯一一次开根，误差 1e-16 级
return
sys.stdout.write("-1\n") # 所有点都吃进来还不够 S，无解
main()
精度分析（这题的核心）：
| 步骤 | 是否有误差 |
|---|---|
| \(x^2 + y^2\) | ❌ Python 整数，精确。最大 \(2\times10^{18}\) |
| 排序 | ❌ 整数比较 |
| 前缀和 \(\le 10^5 \times 2^{31} \approx 2\times10^{14}\) | ❌ 整数 |
最后一次 sqrt |
✅ 唯一的浮点操作，相对误差 \(\approx 10^{-16}\) |
题目只要求 \(10^{-6}\) 的相对误差，\(10^{-16}\) 绰绰有余。
如果换成实数二分半径会怎样？ 每轮二分要 \(O(n)\) 扫描数点，做 50 轮就是 \(5\times10^6\) 次 Python 层迭代， 6 秒限制下勉强；而且二分出的 \(r\) 只有 \(10^{-9}\) 量级的绝对精度， 在 \(r \approx 1.4\times10^9\) 时相对精度不够。排序法在两个维度上都完胜。
complex在这题不能用：\(|x| \le 10^9\)，abs(p)得到的float只有 53 位尾数， 两个距离极其接近的点排序时可能被判成相等，从而选错答案。 这是 110.2 那条警告的实战版本。
BISHI15 小红的夹吃棋（简单）¶
\(3\times3\) 棋盘，
*黑子、o白子、.空。 若某棋子在横向或纵向上被对方两子夹住（三连中间为对方棋子），该子被「夹吃」。 仅一方有子被夹吃 → 对方获胜（黑被吃输出yukari，白被吃输出kou），否则draw。 题面见 BISHI15 原题（牛客）。✅ 题解见
solutions/BISHI15.py，已通过官方样例验证。
这题为什么放在计算几何章：它是「方向向量」思想的最小实例。
「横向或纵向的三连」用几何语言说就是：中心格 \(P\)，方向向量 \(\vec{d} \in \{(1,0), (0,1)\}\)， 检查 \(P - \vec d\)、\(P\)、\(P + \vec d\) 三格。\(3\times3\) 棋盘里能当「中间」的格子只有 每行的第 2 列（3 个）和每列的第 2 行（3 个），一共 6 个位置。
import sys
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for i in range(t):
# 每组占 3 行，第 i 组是下标 1+3i 到 3+3i
g = [row.decode() for row in data[1 + 3 * i:4 + 3 * i]]
black_eaten = white_eaten = False
# 方向 (0,1)：横向三连，中间格是 (r, 1)
pos = [(g[r][1], g[r][0], g[r][2]) for r in range(3)]
# 方向 (1,0)：纵向三连，中间格是 (1, c)
pos += [(g[1][c], g[0][c], g[2][c]) for c in range(3)]
# 3x3 棋盘里能当「中间」的位置只有这 6 个，其余格子不可能被夹
for mid, left, right in pos:
# 中间有子、两侧同色且非空、且两侧与中间异色 —— 三个条件缺一不可
if mid != "." and left == right != "." and left != mid:
if mid == "*":
black_eaten = True # 黑子被夹
else:
white_eaten = True # 白子被夹
if black_eaten and not white_eaten:
out.append("yukari") # 只有黑被夹，白方（小紫）赢
elif white_eaten and not black_eaten:
out.append("kou") # 只有白被夹，黑方（小红）赢
else:
out.append("draw") # 都被夹或都没被夹，都算平局
sys.stdout.write("\n".join(out) + "\n")
三个坑：
- 只有横纵，没有斜向——题面明确说「横向或纵向」，别自作主张加对角线；
- 双方都被夹 = 平局，双方都没被夹也是平局，两种情况输出一样；
- 输出的是对手的名字：黑子（小红
*）被夹 → 小紫赢 →yukari。别弄反。
推广到 \(n \times n\) 棋盘：方向向量法就体现价值了—— 枚举每个格子和 4 个方向（或 8 个方向），检查 \(P \pm \vec d\)：
# [片段] DIRS4 = ((0, 1), (1, 0)) # 横、纵（各代表一条线） DIRS8 = ((0, 1), (1, 0), (1, 1), (1, -1)) # 再加两条对角线 for r in range(1, n - 1): for c in range(1, n - 1): for dr, dc in DIRS4: a, b = g[r - dr][c - dc], g[r + dr][c + dc] ...用方向向量代替「写 4 遍相似的 if」是网格题的标准写法， 见 49-模拟、61-BFS广度优先搜索。
110.11 可抄用模板汇总¶
# [片段]
"""计算几何基础工具箱（Python 3.9 兼容）。
用法约定：
- 需要**精确判断**（共线、左右、相交）时用整数版 cross_i / 元组坐标；
- 只需要距离和面积、且坐标 <= 1e7 时用 complex 版，代码更短。
"""
from math import hypot, sqrt
# ---------- complex 版（坐标 <= 1e7）----------
def dot(o, a, b):
"""向量 oa · ob。"""
return ((a - o).conjugate() * (b - o)).real
def cross(o, a, b):
"""向量 oa × ob。> 0 逆时针，= 0 共线，< 0 顺时针。"""
return ((a - o).conjugate() * (b - o)).imag
def rot90(v):
"""逆时针旋转 90 度。"""
return v * 1j
def point_seg_dist(p, a, b):
"""点到线段的距离。"""
if a == b:
return abs(p - a) # 线段退化成点
t = dot(a, p, b) / abs(b - a) ** 2 # 垂足在 ab 上的比例：0 在 a、1 在 b
t = 0.0 if t < 0 else (1.0 if t > 1 else t) # ★ clamp 到 [0,1]，垂足不能跑出线段
return abs(p - (a + t * (b - a))) # a + t*(b-a) 就是线段上离 p 最近的点
# ---------- 整数版（坐标任意大，完全精确）----------
def cross_i(ox, oy, ax, ay, bx, by):
"""整数叉积。"""
return (ax - ox) * (by - oy) - (bx - ox) * (ay - oy)
def dist2_i(x1, y1, x2, y2):
"""距离的平方。比较大小时用它，永远不要开根。"""
dx = x1 - x2
dy = y1 - y2
# 平方是单调映射，比较距离等价于比较距离平方；整数输入则结果精确
return dx * dx + dy * dy
def line_from(x1, y1, x2, y2):
"""两点 -> 一般式 (A, B, C)，满足 A*x + B*y + C = 0。"""
A = y2 - y1
B = x1 - x2
return A, B, -(A * x1 + B * y1)
def point_line_dist(x0, y0, A, B, C):
"""点到直线 Ax+By+C=0 的距离。"""
return abs(A * x0 + B * y0 + C) / hypot(A, B)
def polygon_area2(pts):
"""有符号的**两倍**面积（整数坐标 -> 整数）。正数表示逆时针。"""
s = 0
n = len(pts)
for i in range(n):
x1, y1 = pts[i]
x2, y2 = pts[i + 1 - n] # i == n-1 时取到 pts[-1+... ] = pts[0]
s += x1 * y2 - x2 * y1
return s
def convex_hull(pts):
"""Andrew 单调链求凸包，返回逆时针顶点列表（不含共线点）。O(n log n)。
pts 是 (x, y) 整数元组的列表。n <= 2e5 时 Python 约 1-2 秒。
"""
pts = sorted(set(pts)) # 先去重再按 (x, y) 字典序排；重复点会让叉积恒为 0
if len(pts) <= 2:
return pts # 0/1/2 个点构不成多边形，原样返回
lower = [] # 下凸壳：从最左点走到最右点
for p in pts:
# 栈顶两点与新点若不是严格左转，栈顶就不在凸壳上，弹掉
while len(lower) >= 2 and cross_i(*lower[-2], *lower[-1], *p) <= 0:
lower.pop()
lower.append(p)
upper = [] # 上凸壳：反着再走一遍
for p in reversed(pts):
while len(upper) >= 2 and cross_i(*upper[-2], *upper[-1], *p) <= 0:
upper.pop()
upper.append(p)
# 两条壳的首尾各是同一个端点，各去掉最后一个再拼接，得到逆时针一圈
return lower[:-1] + upper[:-1]
<= 0还是< 0：这一个字符决定共线点留不留。
写法 弹栈条件 结果 cross_i(...) <= 0叉积为 0（共线）也弹 不保留边上的共线点，凸包顶点最少 cross_i(...) < 0只弹真正的右转 保留边上的共线点，凸包边上会多出中间点 上面的模板用
<= 0，给出的是「顶点最少」的凸包，这也是绝大多数题想要的。 什么时候要改成< 0？题目问「凸包边界上有多少个给定点」「周长上的格点数」 这类与边上的点有关的问题时。 ⚠️ 用< 0时若输入有重复点，会因为叉积恒为 0 而永远不弹栈， 所以sorted(set(pts))的去重不能省。
polygon_area2里的pts[i + 1 - n]：\(i < n-1\) 时i+1-n是负数， Python 的负下标从末尾数，恰好等于pts[i+1]；\(i = n-1\) 时是pts[0]。 一行代替了% n，且省掉一次取模。可读性略差，只在热循环里用。
110.12 本章速查¶
| 要点 | 结论 |
|---|---|
| 二维点/向量 | Python 用 complex，运算符全重载好了 |
| 距离 | abs(p - q) / math.dist / math.hypot |
| 逆时针转 90° | p * 1j |
| 点积 | ((a-o).conjugate() * (b-o)).real |
| 叉积 | ((a-o).conjugate() * (b-o)).imag |
conjugate() |
绝对不能省，否则点积叉积都算错 |
complex 的致命限制 |
内部是 float，只有 53 位；坐标 \(\ge 10^8\) 必须改整数 |
| 判共线 / 左右 / 相交 | 一律用整数叉积，零误差 |
| 比较距离 | 比平方，绝不开根 |
| 直线表示 | 只用一般式 \(Ax+By+C=0\)（点斜式竖直线会崩） |
| 两点求一般式 | \(A=y_2-y_1\)，\(B=x_1-x_2\)，\(C=-(Ax_1+By_1)\) |
| 点到直线 | \(\dfrac{\|Ax_0+By_0+C\|}{\sqrt{A^2+B^2}}\) |
| 点到线段 | 投影参数 \(t\) 必须 clamp 到 \([0,1]\) |
| 多边形面积 | 鞋带公式，返回两倍面积保持整数 |
| 圆的覆盖 | \(x^2+y^2 \le r^2\)，全程平方 |
| 「最小半径」类题 | 答案落在某个点的距离上 → 排序 + 前缀和，别二分 |
| 浮点比较 | 用 sgn(x) + EPS，不用 == 0 |
| 数据规模 → Python 现实性（计算几何） |
|---|
| 排序 + 前缀和，\(n \le 3\times10^5\) |
| 逐点叉积，\(n \le 10^6\) |
| 凸包，\(n \le 2\times10^5\) |
| \(O(n^2)\) 枚举点对，\(n \le 3000\) |
| 分治最近点对，\(n \le 10^5\) |