主页 / coding / 问题 / 79446920
Accepted
Linda
Asked: 2025-02-18 09:05:35 +0800 CST

为什么该算法需要 GCD 来发现笛卡尔坐标平面上的所有三点组共线？

  • 772

我正在尝试解决这个编码难题：“给定一个对数组，每对 (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 用于表示斜率，它解决了什么问题？

python

1 个回答

  1. Best Answer

    澄清一下：

    非常感谢no comment同学的指教，楼主贴出的解决方案里的GCD确实是需要的，而我原来的答案是错误的。

    举例来说，和points = [(0, 0), (999999997, 999999998), (999999998, 999999999)]之间的差异仅出现在浮点数未包括的那么多小数位之后，导致被评估为 True。999999997/999999998999999998/999999999999999997/999999998 == 999999998/999999999

    我还发现这个答案很好地讨论了相关主题。

    这个答案已经被标记为接受，所以我无法删除它；我会把它保留在这里作为反例。

    原答案（错误）：

    我猜你的代码的作者正在试图解决浮点表示的不准确性问题。

    但这种担心其实是没有必要的，因为 x 和 y 都是整数，例如 3.0/9.0 == 9.0/27.0 会返回 True，我最近研究了相关主题，因此可以证实这一点。唯一可能遇到麻烦的情况是分母或分子是浮点数，这不适用于您的问题。

    因此，您可以修改解决方案以简单地使用数字斜率，但您需要特别处理 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
    • 4

相关问题