Нужна струкнура данных,

← →
Romkin (2002-01-21 11:50) [5]

Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ.
Как раз там описан метод для поиска наименьшего расстояния между точками, кол-во действий O(n*Log2(n)).
Алгоритм, правда, рекурсивный, так что насчет памяти - как запрограммируешь, но все равно прилично.
Идея такая:
Исходные данные: два массива X & Y, содержащие координаты (x,y)(записи типа TRecord вполне). Массивы упорядочены по возрастанию координат, соотв. x & y.
1. Делим множество точек пополам вертикальной линией (находим медиану массива X) на два L & R. Точки на линии - как хочешь респределяем по половинам. Получаем соотв Xr, Yr & Xl & Yl, также упорядоченные
2. Находим минимальные расстояния между точками половин (рекурсивно, те тоже дробя их пополам и тд), Dr & Dl соотв.
Находим минимальное расстояние из этих двух: D.
3. На основе Y создаем массив Yd, содержащий точки, расстояние по х которых от линии не более D (упорядоченный по y). Проходя по этому массиву снизу вверх, вычисляем для каждой точки расстояние до 7 следующих (обоснование семи - в книге).
Соответственно, минимальное из этих расстояний - минимальное для двух половин. Если гарантируется, что точки не совпадают, имхо, можно ограничится 5 точками.
Все делается рекурсивно, первоначально массивы удобно упорядочить QuickSort (demos\threads). Потом надо делить так, чтобы постоянно получались уже упорядоченные. Впрочем, поскольку по условию задачи входной массив почти упорядочен, QuickSort подходит плохо, упорядочивать лучше другими алгоритмами.

Нужна струкнура данных, Найти похожие ветки