为何在寻找笛卡尔平面中共线三点组的算法中需要使用GCD？

咱们先搞懂这个算法的核心逻辑：对于每个点i，我们统计其他所有点j相对于i的斜率，斜率相同的点j们都和i在同一条直线上。如果有k个点和i的斜率相同，那从这k个点里选2个和i组合，就能得到math.comb(k,2)个共线三点组。

那问题来了，怎么准确表示斜率？如果直接用两点的纵坐标差dy和横坐标差dx来代表斜率，会出大问题！比如：

• 点i到点j的dy=4，dx=2，斜率是2
• 点i到点k的dy=2，dx=1，斜率也是2

这两个点对明明是同一个斜率，但如果直接把(4,2)和(2,1)作为字典的键，字典会把它们当成两个不同的条目，导致我们统计到的相同斜率的点对数量少了，最后算出来的共线组数就会出错。

这时候GCD（最大公约数）就派上用场了！它的作用就是把dy和dx约分成最简整数比：

• 对于(4,2)，GCD是2，4÷2=2，2÷2=1，得到(2,1)
• 对于(2,1)，GCD是1，直接得到(2,1)

这样一来，所有斜率相同的点对都会被转换成同一个最简键，字典就能正确统计出和点i同斜率的点的数量了。

再举个反例，如果不用GCD会怎么样？假设我们有三个共线点：i(0,0)、j(2,4)、k(1,2)。统计i的斜率时，j对应的键是(4,2)，k对应的键是(2,1)，字典里会有两个键，每个的出现次数都是1。这时候计算math.comb(1,2)的结果是0，我们就漏掉了这组共线的三点，结果自然不对。

另外，GCD还能处理负数的情况：比如dy=-4，dx=-2，GCD是2（或者说-2，取决于GCD函数实现），约分后得到(-4÷(-2), -2÷(-2))=(2,1)，和正数的情况一致，不会因为符号不同被当成不同的斜率。

总结一下，用GCD的核心目的就是统一相同斜率的表示形式，避免因为dy和dx的倍数关系或者符号问题，把同一个斜率当成不同的键来统计，确保我们能准确计算出共线的三点组数量。

备注：内容来源于stack exchange，提问作者Linda