149. Max Points on a Line

https://leetcode.com/problems/max-points-on-a-line/

基本思路是,按照"斜率+截距"聚合,然后计算每个group下面有多少个点。实现上有两个需要注意的地方:

我觉得这里的斜率和截距代码可以作为模板使用

def norm(x, y):
    m = gcd(x, y)
    return x // m, y // m

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
        return a

x = ps[i][0] - ps[j][0]
y = ps[i][1] - ps[j][1]
if x == 0:
    ft = (1, 1 << 30, 1, ps[i][0])
elif y == 0:
    ft = (1, 0, 1, ps[i][1])
else:
    a, b = slp = norm(x, y)
    cut = norm(ps[i][1] * a - ps[i][0] * b, b)
    ft = (slp, cut)