LC 149. Max Points on a Line

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

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

处理重复点
计算斜率和截距

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

结果是个4元组 (a, b, c, d)
b / a 表示斜率
d / c 表示截距
对于垂直线的话表示特殊些，是x轴而非y轴的截距，不过并不会产生混淆

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)