Район по соседям
У n перекрёстков города известно, к какому району они относятся. Для q новых точек нужно назвать район голосованием k ближайших соседей — так, как в статье, и со всеми её правилами, чтобы ответ был единственным:
- расстояние — обычное, по прямой;
- соседи упорядочены по расстоянию, а при равном расстоянии — по номеру перекрёстка во входе (раньше — значит ближе); голосуют первые k;
- побеждает район, за который подано больше всего голосов; если таких районов несколько — тот из них, чей перекрёсток стоит в списке соседей раньше всех.
Один из тестов — настоящие перекрёстки центра Алматы с районами по границам из OpenStreetMap: две тысячи известны, о тысяче других спрашивают.
Вход
В первой строке числа n и k (1 ≤ k ≤ n ≤ 2000). В каждой из следующих n строк — целые x, y (|x|, |y| ≤ 10⁶) и номер района c (1 ≤ c ≤ 20). Затем число вопросов q (1 ≤ q ≤ 1000) и q строк с целыми координатами точек.
Выход
Для каждого вопроса — номер района в отдельной строке.
Примеры
Пример 1
7 4 60 80 2 90 -120 1 -108 144 1 -132 -176 2 0 260 3 180 240 3 -192 256 3 3 0 0 500 500 -100 0
2 3 1
Пример 2
25 2 0 0 1 100 0 2 200 0 3 300 0 1 400 0 2 0 100 3 100 100 1 200 100 2 300 100 3 400 100 1 0 200 2 100 200 3 200 200 1 300 200 2 400 200 3 0 300 1 100 300 2 200 300 3 300 300 1 400 300 2 0 400 3 100 400 1 200 400 2 300 400 3 400 400 1 5 50 50 200 200 250 150 0 0 450 450
1 1 2 1 1
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Корень извлекать не нужно: порядок соседей по квадрату расстояния тот же, а квадраты целых координат — целые числа, и сравнения точные.
2Подсказка 2
Посмотрите на первый пример: при k = 4 у Алмалинского (1) и Медеуского (2) районов по два голоса. Какой из них назовёт ваша программа и почему? Привычные «самый частый» в библиотеках выбирают при ничьей первый подсчитанный, а не ближайший.
3Идея
Это метод k ближайших соседей в чистом виде. Вся трудность — в правилах: соседей сортируют по паре (квадрат расстояния, номер), а при равенстве голосов проходят по соседям от ближнего к дальнему и берут первый район, у которого максимум голосов.
4Разбор
Для каждого вопроса считаем пары (d², номер) для всех известных перекрёстков и выбираем k наименьших: в Python — heapq.nsmallest, на Go — короткий упорядоченный список, куда новая пара вставляется, только если она меньше последней. Сравнение пар само упорядочивает равные расстояния по номеру. Потом считаем голоса и ещё раз проходим по соседям в том же порядке: первый, чей район набрал максимум, и есть ответ.
На тесте с Алматы голосование пяти соседей ошибается лишь у перекрёстков возле границ районов — как в сцене статьи.
4+Решение
5Сложность
O(n log k) на вопрос, O(q·n log k) всего: до двух миллионов расстояний.
6Типичные ошибки
- Ничья в пользу меньшего номера.
Counter.most_commonиmaxпо словарю выбирают при равенстве тот район, который встретился в подсчёте первым, а не ближайший. Первый пример это ловит. - Неустойчивая сортировка соседей. Если сортировать только по расстоянию, равноудалённые перекрёстки (во втором тесте их много — сетка) могут встать в любом порядке, и при k на границе голосуют не те.