Ваша задача — найти ближайшую пару точек из заданного множества.
В компьютерных графике и зрении есть множество вариантов применения этой задачи из вычислительной геометрии. Примитивный алгоритм с квадратичным временем выполнения делает итерации, проходя через все пары точек, чтобы найти ближайшие друг к другу. Ваша цель — спроектировать алгоритм «разделяй и властвуй», время выполнения которого составит .
Чтобы решить эту задачу за время , разобьём с помощью правильно подобранной вертикальной линии данные точек пополам — множества и размера . Ради простоты предположим, что все координаты для данных точек различные и количество точек чётное. С помощью двух рекурсивных вызовов с параметрами и мы находим минимальные расстояния и в этих поднаборах. Пусть .
Остаётся проверить, существуют ли такие точки и , при которых расстояние между ними меньше . Мы не можем себе позволить проверять все возможные такие пары, так как их . Для более быстрой проверки мы отбросим все точки из и , расстояние которых от центральной линии по больше, чем . Таким образом, мы сосредотачиваемся на следующей полосе:
💡 Остановитесь и подумайте:
Почему мы можем сузиться до этой полосы?
Теперь отсортируем точки из полосы по координатам и обозначим получившийся отсортированный список . Оказывается, что если , то расстояние между точками и однозначно будет больше . Упражнение ниже это демонстрирует.
✒️ Упражнение:
Разделите полосу на квадратов, как показано ниже, и продемонстрируйте, что каждый из таких квадратов содержит максимум четыре точки ввода.
Это приводит к следующему алгоритму. Сначала мы сортируем данные нам точек по их координатам , затем делим получившийся отсортированный список на две половины и размера . Находим минимальные расстояния и с помощью рекурсивных вызовов для каждого из наборов и . Пусть . Тем не менее наша работа ещё не закончена, потому что нам также нужно найти минимальное расстояние между точками из разных наборов (то есть точкой из и точкой из ) и проверить, ниже ли это расстояние, чем . Чтобы в этом убедиться, мы отфильтруем изначальный набор и оставим только точки с дистанцией по до средней линии, не превышающей . После этого мы сортируем набор точек в получившейся линии по координатам и сканируем получившийся список. Вычислим расстояние от каждой точки до семи последующих точек списка и вычислим — минимальное расстояние, которое нам встретилось во время сканирования. Затем выведем .
Время выполнения алгоритма соответствует рекуррентному соотношению.
— результат сортировки точек в полосе по координате при каждой итерации.
✒️ Упражнение:
Проанализируйте рекурсивное дерево алгоритма и докажите, что .
✒️ Упражнение:
Продемонстрируйте, как избежать сортировки при каждом рекурсивном вызове и понизить время выполнения до .
- Формат ввода: Первая строка содержит точек. Каждая из следующих строк определяет точку .
- Формат вывода: Минимальное расстояние.
- Ограничения: ; — целые числа.
- Примеры
Пример 1
|
Ввод |
Вывод |
|
2 |
5.0 |
Пример 2
|
Ввод |
Вывод |
|
11 |
1.414213 |
- Во втором примере самое маленькое расстояние — . Есть две пары точек на этом расстоянии. Ниже они выделены голубым и красным: и ; и .
Помните, что расстояние между точками и равно . Так, хотя ввод и содержит только целые числа, ответ не обязательно будет целым числом, и потому вам нужно обратить внимание на точность при выводе результатов. Абсолютное значение разницы между ответом вашей программы и оптимальным значением не должно превышать . Для этого ваш ответ должен содержать не меньше четырех цифр в дробной части. Иначе даже правильно вычисленный результат может не пройти нашу систему проверки из-за ошибок при округлении.
💡 Совет: по возможности старайтесь избегать использования чисел с плавающей дробной частью, при необходимости используйте встроенные алгоритмы для сортировки.