Trouver la ligne qui contient un maximum de points équidistantes

Question

Compte tenu de R (lignes), C (coloumns), N cordinates (x, y) où x < = R & & y < = C, nous avons besoin de trouver la ligne qui contient le maximum de points mutuellement équidistants. La cible ultime est de trouver le nombre de ces points sur cette ligne. Par équidistance mutuelle, cela signifie que tous les points de cette ligne doivent être à égale distance de son point voisin. Exemple: (1,1), (3,3), (5,5), (7,7), (9,9).

Nous n'avons pas besoin de considérer les lignes qui contiennent des points non équidistants les uns des autres. Exemple: (1,1), (2,2), (4,4).

J'ai essayé de le résoudre en utilisant une approche proche de N^3 mais il n'a pas pu passer tous les cas de test.

Mon approche:

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 

Y at-il une meilleure approche?

Answer 1

Une manière simple de le faire est d'essayer chaque ligne possible en choisissant de commencer deux points, et de vérifier le point suivant aussi dans les points d'entrée. Pour ce point de stockage dans un ensemble de structure (la vérification plus rapide est point dans).

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)