Неслабое звено (НТО 21/22 :: ИЭС)
Легенда
После сетевой инвентаризации компания «Энергия хаоса» приступила к работам по повышению отказоустойчивости, а именно — соединению отдельных своих сетей в одну целую. Для этого им необходимо построить линии электропередачи между изолированными сетями. В распоряжении компании есть всё та же информация о построенных между крупными узлами линиях электропередачи, а также координаты этих узлов на условной декартовой плоскости. Используя эту информацию, определите узлы, между которыми нужно построить ЛЭП, чтобы объединить изолированные сети в одну. При этом суммарная длина прокладываемых ЛЭП должна быть минимальной.
Входной формат: два списка. Первый — список координат узлов (до 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