问题：

N点给出在2维平面。什么是分在同一的直接的行的最大个数？

N points are given on a 2-dimensional plane. What is the maximum number of points on the same straight line?

这个问题有O（N 2 ）解决方案：通过每个点，找到具有相同点数DX / DY 与相对于当前点。商店 DX / DY 关系哈希映射效率。

The problem has O(N2) solution: go through each point and find the number of points which have the same dx / dy with relation to the current point. Store dx / dy relations in a hash map for efficiency.

有没有这个问题更好的解决方案比O（N 2 ）？

Is there a better solution to this problem than O(N2)?

推荐答案

有可能没有办法解决这个问题，它比计算的标准型号为O（n ^ 2）显著更好。

There is likely no solution to this problem that is significantly better than O(n^2) in a standard model of computation.

发现三点共线点的问题简化为发现，经过积分最高的行，发现三点共线点的问题是3SUM硬，这意味着解决它在不到为O（n ^ 2）时间会是一个重大的理论成果。

The problem of finding three collinear points reduces to the problem of finding the line that goes through the most points, and finding three collinear points is 3SUM-hard, meaning that solving it in less than O(n^2) time would be a major theoretical result.

见$p$pvious 的问题，在发现三点共线点。

See the previous question on finding three collinear points.

供您参考（利用已知的证明），假设我们要回答3SUM问题，如寻找X，Y，Z的列表中移除x，使得X + Y + Z = 0。如果我们有一个快速算法共线点的问题，我们可以使用算法来解决3SUM如下问题。

For your reference (using the known proof), suppose we want to answer a 3SUM problem such as finding x, y, z in list X such that x + y + z = 0. If we had a fast algorithm for the collinear point problem, we could use that algorithm to solve the 3SUM problem as follows.

有关在X各自的x，创建点（x中，x ^ 3）（现在，我们假定X的元素是不同的）。接下来，检查是否存在从创建点之间存在三点共线点。

For each x in X, create the point (x, x^3) (for now we assume the elements of X are distinct). Next, check whether there exists three collinear points from among the created points.

要看到这个作品时，请注意，如果X + Y + Z = 0，则该行从x和y的斜率

To see that this works, note that if x + y + z = 0 then the slope of the line from x to y is

（Y ^ 3 - X ^ 3）/（Y - X）= Y ^ 2 + YX + X ^ 2

(y^3 - x^3) / (y - x) = y^2 + yx + x^2

和行从x到z的斜率是

（Z ^ 3 - X ^ 3）/（Z - X）= Z ^ 2 + ZX + X ^ 2 =（ - （X + Y））^ 2 - （X + Y）X + X ^ 2 = X ^ 2 + 2XY + Y ^ 2 - X ^ 2 - XY + X ^ 2 = Y ^ 2 + YX + X ^ 2

(z^3 - x^3) / (z - x) = z^2 + zx + x^2 = (-(x + y))^2 - (x + y)x + x^2 = x^2 + 2xy + y^2 - x^2 - xy + x^2 = y^2 + yx + x^2

相反，如果斜率从x到y的从x到z然后等于斜率

Conversely, if the slope from x to y equals the slope from x to z then

Y ^ 2 + YX + X ^ 2 = Z ^ 2 + ZX + X ^ 2，

y^2 + yx + x^2 = z^2 + zx + x^2,

这意味着

（Y - Z）（X + Y + Z）= 0，

(y - z) (x + y + z) = 0,

所以无论是Y = Z或Z = -x - Y为足以证明的减少是有效的

so either y = z or z = -x - y as suffices to prove that the reduction is valid.

如果有位于X重复，你先检查X + 2Y = 0对任意x和重复的元素y的值（以线性时间使用哈希或为O（n LG电子n）的时间使用排序），然后才删除重复减少了线的点发现的问题。

If there are duplicates in X, you first check whether x + 2y = 0 for any x and duplicate element y (in linear time using hashing or O(n lg n) time using sorting), and then remove the duplicates before reducing to the collinear point-finding problem.