为什么在此算法中需要GCD，发现所有三个点的所有组都是在笛卡尔坐标平面中的？

Question

I试图解决这一编码挑战：“给定一对（x，y）的一对（x，y），它们都是整数，表示笛卡尔坐标平面中一个点的坐标，发现许多三个点的组都是共线。”

事实证明，下面是正确的算法：

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def how_many_3point_in_line( points ):
    ans = 0
    n = len( points )
    for i in range( n - 2 ):
        slopes = defaultdict( int )
        for j in range( i + 1, n ):
            dy, dx = points[i][1] - points[j][1], points[i][0] - points[j][0]
            gcd_num = gcd( dx, dy )
            slopes[( dy // gcd_num, dx // gcd_num )] += 1
        for _, occ in slopes.items():
            ans += math.comb( occ, 2 )
    return ans

明显使用GCD代表斜率，它解决了什么问题？

Answer 1

我猜测您的代码的作者正在尝试解决浮点表示的不准确性。

但是，考虑到X和Y都是整数，例如3.0/9.0 == 9.0/27.0会给您带来真实，这实际上是不必要的。您（可能或不会）遇到麻烦的唯一情况是您的问题不适用于0.3/0.9。

因此，您可以修改解决方案以简单地使用数字斜率，但是您需要特别处理DX为0：

的情况。

def how_many_3point_in_line( points ):
    ans = 0
    n = len( points )
    for i in range( n - 2 ):
        slopes = defaultdict( int )
        numVertical = 0
        for j in range( i + 1, n ):
            dy, dx = points[i][1] - points[j][1], points[i][0] - points[j][0]
            if dx != 0:
                slopes[dy / dx] += 1
            else:
                numVertical += 1
        for _, occ in slopes.items():
            ans += math.comb( occ, 2 )
        ans += math.comb( numVertical, 2 )
    return ans