Дальность дрона
Служба доставки возит лекарства по сёлам дронами. Дрон летит по прямой от села к селу и заряжается в каждом селе, где садится, поэтому дальность полёта ограничивает только длину одного перелёта, а не весь маршрут. Диспетчеру приходят вопросы «какая нужна дальность, чтобы долететь из села a в село b?» — найдите для каждого вопроса наименьшую такую дальность. Садиться можно в любых сёлах из списка, сколько угодно раз.
Два теста — настоящие 675 городов и сёл Южноморавского края из справочника GeoNames на плоскости, в метрах; село номер 1 — Брно. В одном из них двести тысяч вопросов.
Вход
В первой строке n и q (1 ≤ n ≤ 1000, 1 ≤ q ≤ 200 000) — число сёл и вопросов. Дальше n строк с координатами сёл x и y — целые числа, |x|, |y| ≤ 10⁶; сёла могут совпадать. Затем q строк с номерами сёл a и b (1 ≤ a, b ≤ n).
Выход
Для каждого вопроса — наименьшая дальность в тех же единицах, с тремя знаками после точки (ответ засчитывается с относительной погрешностью 10⁻⁶). Если a = b, лететь никуда не нужно, и ответ 0.
Примеры
Пример 1
6 5 0 0 4 3 8 0 30 0 34 4 16 20 1 3 1 4 6 2 5 4 3 3
5.000 22.000 20.809 5.657 0.000
Пример 2
4 4 0 0 5 0 6 0 20 0 1 4 4 1 2 3 2 2
14.000 14.000 1.000 0.000
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Для одного вопроса можно двоичным поиском перебрать дальность и проверять обходом графа, где рёбра — пары сёл не дальше неё. Но вопросов двести тысяч. Какая структура отвечает сразу на все «сколько нужно, чтобы связать»?
2Подсказка 2
В статье о минимальном остовном дереве доказано: путь по остову между двумя вершинами делает самое длинное ребро на пути наименьшим возможным. Остаётся быстро узнавать самое длинное ребро на пути по дереву.
3Идея
Ответ на вопрос (a, b) — самый длинный провод на пути между a и b в минимальном остовном дереве. Меньше нельзя: если выбросить из дерева этот провод, a и b окажутся в разных частях, и любой маршрут дрона перелетает между частями хотя бы раз, а самый короткий такой перелёт — как раз выброшенный провод. Больше не нужно: путь по дереву и есть маршрут. Дерево строится один раз, а дальше каждый вопрос — про путь в дереве.
4Разбор
Граф полный, поэтому остов удобно строить Примом без кучи за O(n²), на квадратах расстояний — они целые и сравниваются точно. Потом для каждого села, из которого задан хотя бы один вопрос, обойдём дерево из этого села и запишем для всех остальных самое длинное ребро на пути: у соседа оно равно максимуму из значения у текущей вершины и длины ребра между ними. Обход — O(n), всего не больше n обходов, O(n²), и после этого каждый вопрос — одно обращение к таблице. Корень берём при печати.
Есть и другие способы. Можно разложить вопросы по сёлам и обойтись без таблицы на миллион чисел. Можно двоичными подъёмами по дереву отвечать за O(log n) на вопрос — так делают, когда сёл миллион и таблица в память не влезет. Можно вообще не строить дерево отдельно: идти Краскалом по проводам и в момент, когда a и b впервые оказались в одном куске, записать длину провода — это ответ; вопросы при этом хранят в кусках системы непересекающихся множеств и при слиянии перекладывают из меньшего куска в больший.
На Моравии ответ для любого вопроса о Брно — 5644,887 м: ближе этого у Брно в справочнике соседей нет, так что любой маршрут из Брно начинается с перелёта не короче.
4+Решение
5Сложность
O(n²) на остов и обходы и O(1) на вопрос: O(n² + q) в сумме. Обход дерева на каждый вопрос — O(n·q), больше ста миллионов шагов в четвёртом тесте.
6Типичные ошибки
- Кратчайший путь вместо остова. Самый короткий маршрут по сумме длин — прямой перелёт, и его длина почти всегда больше ответа. В первом примере из села 1 в село 3 по прямой 8, а с посадкой во втором селе хватает дальности 5.
- Обход на каждый вопрос. Идея верная, но двести тысяч обходов дерева из 675 вершин не успеют.
- Самый длинный провод всего остова. Он нужен, только если путь через него проходит; во втором примере из села 2 в село 3 хватает единицы.