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

Ближайшие города

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

Сервис погоды присылает прогноз для ближайшего к пользователю города, а когда город неясен — для нескольких ближайших на выбор. Городов десятки тысяч, запросов — тысячи в секунду. Дан список городов — точек на плоскости — и запросы: точка и число k. Для каждого запроса выведите k ближайших городов по обычному расстоянию на плоскости, от ближнего к дальнему. Если расстояния равны, раньше идёт город с меньшим номером.

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

Вход

В первой строке число городов n (1 ≤ n ≤ 50 000), дальше n строк с их координатами x y; города нумеруются с единицы в порядке ввода, у разных городов координаты могут совпадать. Затем число запросов q (1 ≤ q ≤ 10 000) и q строк x y k, где 1 ≤ k ≤ min(5, n). Все координаты целые, |x|, |y| ≤ 10⁷.

Выход

Для каждого запроса в отдельной строке — номера k ближайших городов через пробел, от ближнего к дальнему.

Примеры

Пример 1

Вход

Выход

Ограничения

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

Разбор

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

1Подсказка 1

Перебор всех городов для каждого запроса — 50 тысяч на 10 тысяч, полмиллиарда расстояний. Нужна структура, которая сразу отбрасывает далёкие куски карты. Подумайте о двоичном дереве, где каждый узел делит плоскость прямой на две половины.

2Подсказка 2

В k-d дереве ищем так: сначала спускаемся в ту половину, где лежит запрос, а в другую заходим, только если она может содержать кого-то ближе k-го лучшего из найденных. Как проверить это одним числом? И что будет, если запрос далеко от всех городов — например, все города на одной прямой, а запрос в стороне от неё?

3Идея

Строим k-d дерево: узел — медиана по той оси, вдоль которой точки поддерева разбросаны шире. Для каждого узла храним прямоугольник, в котором лежит всё его поддерево. Поиск — обход в глубину: держим кучу из k лучших с худшим на вершине и заходим в поддерево, только если расстояние от запроса до его прямоугольника не больше, чем до худшего из k лучших. Ближнего ребёнка смотрим первым — так лучшие находятся раньше и отсекают больше.

4Разбор

Дерево. Сортируем точки поддерева по выбранной оси, медиана становится узлом, половины — детьми. Прямоугольник узла — объединение его точки и прямоугольников детей. Глубина дерева — log₂ n, построение — O(n log² n) с сортировкой на каждом уровне.

Отсечение. Квадрат расстояния от запроса до прямоугольника: по каждой оси — насколько запрос левее левого края или правее правого (иначе ноль), и сумма квадратов. Ближе этого в поддереве никого нет. Если куча полна и это расстояние строго больше расстояния до худшего в куче, поддерево пропускаем. Равные не пропускаем: там может быть город на том же расстоянии с меньшим номером.

Почему прямоугольник, а не прямая. Классическое отсечение сравнивает с лучшим только расстояние до разделяющей прямой узла. Если запрос далеко от всех городов, а города лежат на одной прямой, как в пятом тесте, лучший найденный город далёк, и полоса такой ширины задевает почти все прямые деления — поиск обходит всё дерево. Расстояние до прямоугольника учитывает и то, насколько запрос в стороне, и отсекает правильно.

Все расстояния — целые квадраты, до 8·10¹⁴, без корней и без чисел с плавающей точкой.

4+Решение

5Сложность

Построение O(n log² n), память O(n). Запрос — в среднем около log n + k узлов на равномерно разбросанных точках; гарантии в худшем случае у k-d дерева нет, но с прямоугольниками и делением по более широкой оси тесты этой задачи проходят быстро.

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

Перебор всех городов. Верно, но 50 тысяч городов на 10 тысяч запросов не уложатся во время. Это неверное решение задачи.
Строгое отсечение. Если пропускать поддерево при равенстве расстояний, потеряется город на том же расстоянии с меньшим номером: в четвёртом тесте на каждом узле сетки стоят десятки городов.
Оси по очереди. Если делить по x и y строго по очереди, у городов на одной прямой половина делений придётся на ось, где все координаты равны: такое деление ничего не разделяет, и поиск часто заходит в обе половины.
Расстояние в double. Для сравнения хватает квадратов в целых числах; корень и плавающая точка только добавляют ничьих, которых нет.

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

GEO Структура данных k-d дерево Двоичное дерево, которое делит пространство по осям по очереди: ближайшая точка — за десятки шагов вместо перебора. O(n log n) построение; O(log n) на запрос в среднем 1 задача DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи