Microsoft LC149 一条直线最多点数：有理斜率规范化

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入整数坐标列表，返回某条无限直线上最多能包含多少输入点；重复坐标视为多个输入点。
• 两点决定直线，同一锚点相同坐标的点单独计 duplicates。
• 若原面试要求线段、误差容忍或浮点坐标，需换模型，不能套当前精确有理斜率键。

解题路线

1. 逐点选锚 a，对后续每个不同坐标点 b 求向量 (dx,dy)，用 gcd(|dx|,|dy|) 约成最简整数对。
2. 统一符号，让 dx>0，竖线用 (0,1)、水平线用 (1,0)；这样同方向与反方向共用一条线键，且不使用浮点除法。
3. 锚点相同坐标增加 duplicates，它能加入锚点通过的任何直线。该锚的最好直线点数为 1+duplicates+最大斜率桶计数。
4. 遍历所有锚点保证最优直线至少在某锚处被统计；没有两个不同坐标时答案就是重复点总数。

手动走一遍

点 (0,0)、(1,1)、(2,2) 的方向约分均为 (1,1)，答案 3；(0,0) 与 (0,2) 的竖线键是 (0,1)。若 (0,0) 出现两次，两份都计入通过该坐标的最佳直线。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Maximum points on one geometric line, with exact normalized slopes."""

from collections import defaultdict
from math import gcd


def max_points_on_line(points: list[tuple[int, int]]) -> int:
    if len(points) < 3:
        return len(points)
    best = 0
    for index, (x, y) in enumerate(points):
        count_by_slope = defaultdict(int)
        duplicates = 0
        for other_x, other_y in points[index + 1 :]:
            dx, dy = other_x - x, other_y - y
            if dx == 0 and dy == 0:
                duplicates += 1
                continue
            divisor = gcd(abs(dx), abs(dy))
            dx //= divisor
            dy //= divisor
            if dx < 0 or (dx == 0 and dy < 0):
                dx, dy = -dx, -dy
            count_by_slope[(dx, dy)] += 1
        best = max(best, 1 + duplicates + max(count_by_slope.values(), default=0))
    return best

复杂度

n 个点，每个锚扫描至多 n−1 个点，O(n²) 次斜率处理；gcd 对坐标差大小 D 需 O(log D)，最坏 O(n² log D) 时间，单锚桶 O(n) 空间。

易错点与追问

容易失分的边界

• 用浮点 dy/dx 作 key，精度与竖线都出问题。
• 只约分不统一正负号，把同一条线拆两桶。
• 重复坐标造成 gcd(0,0) 或被误算为新斜率。
• 输入只有 0/1/2 点时边界返回不正确。

继续深挖

• 坐标变成浮点近似值时如何定义共线？
• 若要返回直线方程而非点数，怎样规范化 A x+B y+C=0？
• 数据流持续加点能否高效维护全局最大共线数？