Задачник Базовый курс EN

Пары ближе r

ближайший сосед точки на плоскости хеширование геоданные подсчёт вариантов

Сейсмолог ищет в каталоге землетрясения, которые случились почти в одном месте: повторные толчки, рои, дубли записей. Для начала он хочет знать, сколько вообще пар эпицентров лежит не дальше r друг от друга. Даны точки на плоскости и число r; посчитайте пары точек, расстояние между которыми не больше r.

Второй тест — все землетрясения силой от 5 за 2015–2025 годы из каталога USGS, третий — 45 227 городов мира от 10 тысяч жителей из справочника GeoNames; и те и другие — как точки (долгота, широта) в тысячных долях градуса, без учёта того, что Земля круглая.

Вход

В первой строке число точек n (1 ≤ n ≤ 100 000) и расстояние r (1 ≤ r ≤ 10⁹). Дальше n строк с координатами x y — целыми, |x|, |y| ≤ 10⁹. Точки могут совпадать. Гарантируется, что ответ не больше 10⁶.

Выход

Число неупорядоченных пар точек на расстоянии не больше r.

Примеры

Пример 1

Вход

Выход

Ограничения

Время · Python: 6000 мс
Время · Go: 1500 мс
Память: 256 МБ
Проверка: 9 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Все пары — до 5·10⁹ проверок. Но пара на расстоянии не больше r не может быть «где угодно»: точки близки и по x, и по y. Как разложить точки так, чтобы для каждой быстро найти тех, кто рядом?

2Подсказка 2

Разложите точки по квадратам сетки со стороной r. Где может лежать точка на расстоянии не больше r от данной? И как не посчитать одну и ту же пару дважды?

3Идея

Квадрат точки — (⌊x/r⌋, ⌊y/r⌋). Две точки на расстоянии не больше r отличаются по каждой координате не больше чем на r, значит, их квадраты — тот же самый или соседние, включая соседей по диагонали. Храним квадраты в хеш-таблице: квадрат → его точки. Каждую пару квадратов смотрим один раз: квадрат сам с собой (пары внутри) и с четырьмя соседями «вперёд» — справа сверху, справа, справа снизу и сверху. Остальные четыре соседа — это чьи-то «вперёд», их пары посчитаются там.

4Разбор

Внутри квадрата перебираем пары, с соседями — все сочетания, и для каждой проверяем (Δx)² + (Δy)² ≤ r² в целых числах. Номер квадрата для отрицательных координат удобно считать с округлением вниз — в Python это //; в Go деление округляет к нулю, и квадрат у нуля вышел бы вдвое шире. Ответ от этого не испортился бы — важно лишь, чтобы ни один квадрат не был уже r, — но проверок стало бы больше.

Это та же сетка, что в поиске ближайшей пары, только сторона квадрата задана заранее, и перестраивать ничего не нужно.

4+Решение

5Сложность

Раскладка — O(n) в среднем. Проверок — столько, сколько пар точек в соседних квадратах. Пары в соседних квадратах лежат на расстоянии меньше 2√2·r, и на данных без особых скоплений их лишь в несколько раз больше, чем пар ближе r: O(n + ответ). На точках, где очень много пар чуть дальше r, работа больше, — поэтому в условии и ограничен ответ.

6Типичные ошибки

Все пары. Верно, но на ста тысячах точек это пять миллиардов проверок.
Только восемь соседей и без «вперёд». Если проверять для каждого квадрата всех восемь соседей, каждая пара из разных квадратов посчитается дважды.
Квадраты уже r. Если сторона квадрата меньше r, близкая точка может оказаться через квадрат, а не в соседнем, и такие пары потеряются.
Строгое неравенство. Нужны пары на расстоянии не больше r; в первом примере четыре пары ровно на расстоянии 5.

Алгоритмы задачи

PAR Алгоритм Ближайшая пара точек Две ближайшие точки из n за n log n: разрез, полоса шириной 2d и семь соседей; сеткой — за n в среднем. O(n log n) 2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи