Районы электросети
Энергосистему края делят на k районов, у каждого будет своя подстанция и своя аварийная бригада. Чтобы авария в одном районе не перекидывалась на соседний, районы хотят развести как можно дальше: зазор разбиения — наименьшее расстояние между двумя сёлами из разных районов, и он должен быть наибольшим возможным. Каждое село — ровно в одном районе, районов ровно k, пустых нет. Найдите наибольший зазор и размеры районов при таком разбиении.
Два теста — настоящие 675 городов и сёл Южноморавского края из справочника GeoNames на плоскости, в метрах; один разбивает край на 10 районов, другой — на 80.
Вход
В первой строке n и k (2 ≤ k ≤ n ≤ 1000) — число сёл и районов. Дальше n строк с координатами сёл x и y — целые числа, |x|, |y| ≤ 10⁶. Все сёла в разных точках. Гарантируется, что разбиение с наибольшим зазором единственно.
Выход
В первой строке — наибольший зазор, с тремя знаками после точки (ответ засчитывается с относительной погрешностью 10⁻⁶). Во второй — размеры k районов этого разбиения через пробел, по невозрастанию.
Примеры
Пример 1
7 3 0 0 3 1 1 4 20 2 24 5 21 9 9 30
17.029 3 3 1
Пример 2
5 2 0 0 10 0 21 0 33 0 46 0
13.000 4 1
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Представьте, что вы соединяете сёла по одному проводу, начиная с самых близких пар, как Краскал, и следите за числом кусков. Что можно сказать о зазоре, когда кусков ровно k?
2Подсказка 2
Зазор разбиения на куски Краскала — это следующий провод, который Краскал проложил бы. Почему лучше не бывает: возьмите любое другое разбиение и две точки, которые у Краскала в одном куске, а там — в разных.
3Идея
Постройте минимальное остовное дерево и разрежьте k − 1 самых длинных его проводов. Куски — районы, а зазор равен самому короткому из разрезанных проводов. Это наилучшее разбиение: в любом другом найдутся два села, которые у нас в одном районе, а там — в разных; путь между ними по остову состоит из проводов не длиннее нашего зазора, и где-то на этом пути он переходит из района в район — значит, у другого разбиения зазор не больше.
4Разбор
Граф полный: провода возможны между любыми двумя сёлами, их до полумиллиона. Сортировать их все можно, но проще и быстрее алгоритм Прима без кучи: массив «самый короткий провод от сети до села», на каждом шаге — село с наименьшим значением, после него — пересчёт значений для остальных. Это O(n²) на всё. Расстояния удобно держать в квадрате: координаты целые, квадраты тоже целые, сравнения точные, а корень нужен один раз — при печати.
Дальше отсортируем n − 1 провод остова и сольём концы всех, кроме k − 1 последних, в системе непересекающихся множеств. Размеры множеств — размеры районов. Условие о единственности означает, что самый короткий разрезанный провод строго длиннее самого длинного оставленного, иначе можно было бы разрезать другой провод той же длины и получить другие районы с тем же зазором.
На настоящей Моравии ответ поучителен: десять «районов» — это один огромный, 23 села у Весели-над-Моравой и восемь одиночек, среди которых Брно и Бржецлав. Метод одиночной связи режет там, где разрыв, а у больших городов в этих данных разрывы самые большие: их городские районы в справочник не вошли.
4+Решение
5Сложность
O(n²) на остов, O(n log n) на сортировку его проводов. Краскал по всем парам — O(n² log n), тоже укладывается, но медленнее.
6Типичные ошибки
- Последний проложенный провод вместо следующего. Если строить Краскалом до k кусков и печатать длину последнего взятого провода, получится самый длинный провод внутри района, а не расстояние между районами. Во втором примере это 12 вместо 13.
- Разрезать k проводов вместо k − 1. Каждый разрез добавляет один кусок, а начинали с одного.
- Корень в сравнениях. Сравнивать расстояния с плавающей точкой можно, но квадраты в целых числах точнее и проще: при равных расстояниях корни могут разойтись в последнем бите.