Легенда

После сетевой инвентаризации компания «Энергия хаоса» приступила к работам по повышению отказоустойчивости, а именно — соединению отдельных своих сетей в одну целую. Для этого им необходимо построить линии электропередачи между изолированными сетями. В распоряжении компании есть всё та же информация о построенных между крупными узлами линиях электропередачи, а также координаты этих узлов на условной декартовой плоскости. Используя эту информацию, определите узлы, между которыми нужно построить ЛЭП, чтобы объединить изолированные сети в одну. При этом суммарная длина прокладываемых ЛЭП должна быть минимальной.

Входной формат: два списка. Первый — список координат узлов (до 100) на декартовой плоскости. Координаты представлены парой (X, Y). Второй — список рёбер (до 160), представленных парами номеров узлов. Узлы нумеруются с 0, их номер соответствует индексу в первом списке. Все эти данные представлены в виде строки, которую можно проинтерпретировать командой eval. Пример формата:

([(0, 0), (1, 1), (2,3)], [(1, 2), (4, 3), (5, 6), (6, 4), (10, 7)])

Выходной формат: число строк, соответствующее количеству новых соединений. В каждой строке два целых числа через пробел, соответствующие номерам соединяемых узлов (нумерация с нуля). Порядок вывода ребёр и перечисления узлов внутри ребра может быть любой. Например,

1 2
4 5
30 10

Решение заcчитывается, если новые соединения делают сеть связной, и суммарная длина рёбер не превышает выданную авторским решением больше, чем на 5%.

Time Limit: 1 секунда

Memory Limit: 256 MB


Видео-разбор

Последнее изменение: Monday, 19 September 2022, 12:38