最大互いに等距離点

Question

与えられるR（行）、C（coloumns）、Nのcordinates（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

簡単な方法は、開始可能な2点を選択して各可能な線を試し、入力点でも次の点を点検することです。そのストアは構造体セット内を指します（より速いチェックはポイントインされます）。

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)