Finding the line which contains maximum mutually equidistant points

Question

Given R(rows), C(coloumns), N cordinates (x,y) where x<=R && y<=C, we need to find the line which contains maximum mutually equidistant points. Ultimate target is to find the count of those points on that line.

By mutually equidistant, it means all the points on that line should be at equal distance from its neighbouring point. Example: (1,1),(3,3),(5,5),(7,7),(9,9).

We need not consider lines which contains non-mutually equidistant points. Example: (1,1),(2,2),(4,4).

I tried solving it using near N^3 approach but it could not pass all the test cases.

My approach:

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

Is there a better approach?

Ante Ante · Accepted Answer · 2017-04-30T10:34:39

Simple way to do it is to try each possible line by choosing starting two points, and check is next point also in input points. For that store points in a structure set (faster checking is point in).

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

1 Answers