Найти 2 точки в плоскости X-Y

Question

У меня есть плоскость XY и точки (xi, yi), где x, y и i - целые числа.Теперь, если я рисую бесконечные линии наклона 1 и -1, я должен найти те 2 точки, которые либо будут лежать на одной линии, либо, если ни одна из них не лежит, то должны вывести:

Случай: если максимум 1 точкалежит на прямой, 2-ая точка должна быть точкой, которая имеет минимальное расстояние от линии.В таких случаях мы можем провести линию точно между этими двумя точками, чтобы минимизировать расстояние.

Я не могу найти решение этой проблемы.Мой подход состоял в том, чтобы посмотреть на точки в противоположных квадрантах, но я не нашел лучшего решения, чем O (n ^ 2).

Answer 1

Во-первых, я бы преобразовал точки в другую систему координат, которая поворачивается на 45 °:

u = x + y
v = x - y

Если исходные точки лежат на линии с наклоном 1, их координата v будетравны.Если они лежат на линии с уклоном -1, их координата u будет равна.

Теперь создайте два списка точек.Один отсортирован по u, другой отсортирован по v.Затем итерируйте все точки.Чтобы найти точку, ближайшую к соответствующей линии, вам просто нужно проверить соседей в отсортированном порядке.Если есть соседи с одинаковыми координатами u / v, все готово.Если нет, найдите соседа с наименьшей разницей u / v и запомните его.Сделайте это для всех точек и сообщите пару с наименьшим расстоянием.