c - 如何确定同一条线上的最大点数？

Question

给定：很多点，每个点都有一个唯一的坐标 (x _i ,y _i )

输出：同一行上的最大点数

这是我的方法：

for i=1..n
    for j=i..n
        get the line determined by point[i] and point[j]
        for k=1..n
            check if point[k] is on this line

但似乎这种方法耗时太长，而且总是超过 OJ 系统的时间限制。

Answer 1

迭代每个点，计算每个其他点的极角，对极角排序

这个成本 O(n^2*lgn)

Answer 2

我还没有实现这个，但你也许可以在 O(n) 中做到这一点。

• 使用哈希图按极角存储点：Map<Double,List<Point>>，Double角度在哪里

• 然后迭代地图，List<Point>用最大长度跟踪。该列表将包含结果。

玩那个。看起来它应该工作。