本文详解 gcd 在判断三点共线问题中的关键作用：它通过将方向向量约分为最简整数比，避免浮点精度误差与重复表示问题，确保斜率比较的数学严谨性与计算可靠性。
本文详解 gcd 在判断三点共线问题中的关键作用：它通过将方向向量约分为最简整数比，避免浮点精度误差与重复表示问题，确保斜率比较的数学严谨性与计算可靠性。
在解决“给定平面上若干整数坐标点，统计有多少组三点共线”这一经典计算几何问题时，一个常见思路是：对每个基准点 (P_i)，枚举其余点 (P_j)，计算向量 (\vec{P_iP_j} = (dx, dy))，并按其方向（即斜率）分组——因为所有与 (P_i) 共线的点，其相对于 (P_i) 的方向向量必成比例，即存在非零实数 (k) 使得 ((dx', dy') = k \cdot (dx, dy))。
然而，若直接用浮点数表示斜率（如 dy / dx），会引入两类致命缺陷：
- 浮点精度丢失：当坐标值很大时（例如接近 (10^9)），两个本质不同的分数（如 (999999997/999999998) 和 (999999998/999999999)）在双精度浮点下可能被四舍五入为同一值，导致错误归并；
-
表示不唯一：向量 ((2,4))、((3,6))、((-1,-2)) 均代表相同方向，但若直接存储
(dy, dx)或dy/dx，它们无法自然哈希等价；而浮点除法还额外引入正负零、NaN 等边界问题。
✅ GCD 的作用正是消除上述问题：
对任意向量 ((dx, dy))（注意：需统一处理符号，通常约定让 dx 非负，若 dx == 0 则令 dy > 0），计算 (g = \gcd(|dx|, |dy|))，再将向量约简为最简整数比：
g = gcd(abs(dx), abs(dy)) # 实际代码中 gcd 已支持负数，但逻辑等价 norm_dx = dx // g norm_dy = dy // g # 进一步标准化符号：确保 norm_dx >= 0；若 norm_dx == 0，则 norm_dy > 0 if norm_dx <p>这样，所有共线向量均映射到<strong>唯一的、规范化的整数对</strong>，可安全用于字典键（<code>defaultdict[int]</code>）计数。</p><p>⚠️ 特别注意边界情况：</p>
- 当
dx == 0（垂直线）：此时gcd(0, dy) = |dy|，约简后得(sign(dy), 0)→ 标准化为(1, 0)； - 当
dy == 0（水平线）：约简后为(0, 1)； - 当
dx == dy == 0：不会发生（因点互异，且j > i，两点不同）。
最终，对每个基准点 (P_i)，若某斜率方向上有 k 个其他点，则这 k 个点两两与 (P_i) 构成共线三点组，组合数为 (\binom{k}{2})。累加所有方向即可得全局答案。
? 总结：GCD 不是“可选优化”，而是保障算法数学正确性的必要步骤——它将无限精度的方向关系，无损压缩为有限、唯一、可哈希的整数标识，彻底规避浮点陷阱与表示歧义。在涉及整数坐标的几何计数问题中，这种基于 GCD 的方向归一化是工业级实现的标准范式。
