博弈与计算几何
本节目标
用异或不变量、区间投影和规范化表示处理离散数学应用。
识别信号
这三题没有统一的代码模板。矩形题要把二维关系拆成坐标投影；Nim 要寻找胜负不变量；共线点要让同一条直线获得唯一表示。共同点是先抛开表面操作，明确什么量必须被保持、什么对象必须规范化。
核心定义与不变量
两个轴对齐矩形有正面积交集，当且仅当 x、y 两个一维投影都严格重叠。普通 Nim 的异或和为零恰是必败态。对固定锚点，任意两点的方向向量经最大公约数约分和符号统一后，是共线关系的稳定键。
朴素方法与瓶颈
枚举矩形内部点、搜索所有游戏后继、对每组三点检查共线，都会引入不必要的规模。投影把二维判断降成常数次比较；异或一次汇总所有石子堆；固定一个点并统计规范化斜率把三重枚举降到二重。
推导与实现框架
先从定义写出可验证条件。矩形以 max(left) < min(right) 判断每个轴；Nim 累计 XOR；直线题对每个锚点统计 (dx, dy)，先处理重复点，再约分、统一垂直线、水平线和整体符号。没有必要把它们强行归成一种算法。
复杂度与数值边界
矩形重叠为 O(1)，Nim 为 O(n)。直线题中，C++ 使用 std::map，时间复杂度为 O(n²(log C + log n))；Python 使用哈希表，平均为 O(n² log C)，其中 log C 来自 GCD。坐标差和 GCD 计算使用足够宽的整数；投影相接时长度为零，不是重叠；重复点不应参与零向量约分。
母题序列
常见误区
- 把边界接触当作矩形“重叠”，忽略正面积要求。
- 把 Nim 的石子总数或奇偶性当作判据。
- 用浮点斜率作哈希键，或让等价斜率拥有不同符号。
- 遇到重复点直接计算 GCD，产生
(0, 0)的无意义方向。
迁移方向
不变量可迁移到其他有限游戏，规范化键可迁移到分数、向量和几何哈希，投影可迁移到区间和盒体相交。本栏不继续扩展 SG 函数、Nim 变体或凸包等高级计算几何。