找到包含最大相互等距点的线

Question

给定 R（行）、C（列）、N 坐标 (x,y)，其中 x<=R && y<=C，我们需要找到包含最大相互等距点的直线。最终目标是找到该线上那些点的数量。

相互等距，这意味着该线上的所有点与其相邻点的距离应该相等。示例：(1,1),(3,3),(5,5),(7,7),(9,9).

我们不需要考虑包含非相互等距点的线。示例：(1,1),(2,2),(4,4).

我尝试使用接近 N^3 的方法解决它，但它无法通过所有测试用例。

我的做法：

For every pair of two points i and j:
 Consider another point k:
     if(slope(i,j) == slope(i,k))
       They are at same line, map these points with the calculated slope.

Set ans = 0.
Then for every slope in the map,
sort all the mapped points and 
check whether they are
mutually equidistant.
If they are mutually equidistant,
and their count is greater than ans,
Set ans=count.
Output = ans

有没有更好的方法？

Answer 1

简单的方法是通过选择开始的两个点来尝试每条可能的线，并检查输入点中的下一个点。对于结构集中的存储点（更快的检查点）。

max_line = []
For every (un-ordered) pair of two points i and j:
  line = [i, j]  # Line starts with i, second point is j
  slope = j - i
  k = j + slope  # Third line point
  while k in points:  # Checking is next line point in
    line.append(k)
    k += slope   # Proceed to next point
  if len(line) > len(max_line):
    max_line = line
print(max_line)

找到包含最大相互等距点的线

Finding the line which contains maximum mutually equidistant points

grid

line

computational-geometry