Нахождение максимального количества равноотстоящих точек на отрезке

Question

Дан набор точек на отрезке прямой.Точки могут лежать в любом месте на линии.Мне нужен аглоритм, чтобы найти максимальное количество точек, которые лежат на прямой через равные промежутки времени.

например, по прямой линии, обозначенной у = 0, у меня могут быть такие точки, как:

[3,0], [1,0], [4,0], [7,0],[11,0], [10,0]

Output : 4 
     [1,0] , [4,0], [7,0], [10,0]

Пример 2:

[2,1], [2,5], [2,3], [2,7], [2,6]

Output: 4
    [2,1], [2,3],[2,5], [2,7]

[Примечание:может иметь любой уклон.Мне нужен только набросок алгоритма.Точки можно считать сохраненными в двумерной матрице], пожалуйста, помогите.

Answer 1

Выберите одну координату с ненулевым (или просто более широким) диапазоном (например, X для первого примера) и отсортируйте ваш набор по этой координате.Затем найдите Самая длинная арифметическая прогрессия

Answer 2

Вот алгоритм перебора в псевдокоде:

for each point X
  for each point Y != X
    find number of connected points from X using the distance between X and Y
  next Y
next X

Как найти количество связанных точек от X, используя расстояние между X и Y:

dXY = Y - X
i = 0
while point_exists(X + i * dXY)
  i = i + 1
end while