Два ближайших города
В справочнике населённых пунктов десятки тысяч записей с координатами. Перед публикацией редактор проверяет, нет ли среди них подозрительно близких — двух записей об одном месте или города и его же района. Начать он хочет с самой близкой пары. Даны точки на плоскости; найдите наименьшее расстояние между двумя из них.
Второй и третий тесты — 45 227 городов мира от 10 тысяч жителей из справочника GeoNames как точки (долгота, широта) в тысячных долях градуса, без учёта того, что Земля круглая: во втором тесте все записи как есть, в третьем каждая точка оставлена один раз.
Вход
В первой строке число точек n (2 ≤ n ≤ 100 000), дальше n строк с координатами x y — целыми, |x|, |y| ≤ 10⁹. Точки могут совпадать.
Выход
Квадрат наименьшего расстояния между двумя точками — целое число.
Примеры
Пример 1
6 0 0 7 1 3 4 10 10 6 5 -2 9
10
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Перебор всех пар — до 5·10⁹ расстояний. Нужно отсекать пары, не считая их. Разрежьте точки вертикальной прямой на две равные половины и решите каждую. Какие пары остались непроверенными?
2Подсказка 2
Пусть d — лучшее расстояние внутри половин. Пара через разрез ближе d может быть только в полосе шириной 2d вокруг разреза. Сколько точек полосы надо сравнить с данной, если идти по полосе снизу вверх?
3Идея
Это алгоритм ближайшей пары «разделяй и властвуй». Точки сортируются по x один раз, рекурсия возвращает свой кусок отсортированным по y — слиянием двух половин. У разреза отбираем точки ближе d по x и каждую сравниваем со следующими по y, пока разница по y меньше d: таких не больше семи.
4Разбор
Всё в целых квадратах: расстояние до разреза сравниваем как (x − xm)² < d², разницу по высоте — как Δy² ≥ d². Квадрат расстояния доходит до 8·10¹⁸ (девятый тест) и помещается в 64-битное целое со знаком.
Почему не хватает соседей по x. Напрашивается ускорение: отсортировать по x и сравнить каждую точку с несколькими следующими. На случайных точках это почти всегда находит ответ, но в шестом тесте точки стоят на девяти высотах по очереди: соседи по x далеко друг от друга по высоте, а ближайшая пара — точки на одной высоте — разделена в порядке по x восемью другими. Окно из восьми её не видит. Полоса с упорядочиванием по y устроена иначе: она смотрит на соседей по высоте, а лемма о семи соседях гарантирует, что их мало.
Совпадающие точки. Во втором и восьмом тестах ответ 0. Алгоритм справляется с ним сам: как только d = 0, полосы пусты, и рекурсия заканчивается быстро.
4+Решение
5Сложность
O(n log n): сортировка и log n уровней рекурсии с линейной склейкой. Если сортировать полосу заново в каждом вызове, выйдет O(n log² n) — тоже проходит, но медленнее.
6Типичные ошибки
- Окно соседей по x. Ошибается на шестом тесте — см. выше.
- Корень и числа с плавающей точкой. Квадраты расстояний до 8·10¹⁸ в
doubleтеряют точность; сравнивайте целые квадраты. - 32-битные числа. Разность координат до 2·10⁹ уже не помещается в 32 бита со знаком, а её квадрат — тем более.
- Полоса из одной половины. Пары внутри половин уже проверены рекурсией, но в полосе нужны точки обеих половин вперемешку, упорядоченные по y: иначе пары через разрез не найдутся.