Перекладка сетей (ОКД НТИ 20/21 :: ИЭС)
Легенда
Прогресс не стоит на месте, в одном микрорайоне потребовалось заменить устаревшую систему ЛЭП на более надёжную. Но энергетика связана с ресурсами, а ресурсы нужно расходовать бережно.
Вам известны координаты точек подключения на условной декартовой плоскости (обусловимся, что первая точка соответствует подстанции, питающей этот микрорайон). Необходимо соединить все точки в новую систему ЛЭП так, чтобы минимизировать суммарную длину проброшенных линий и только её. Линии протягиваются между парами точек, к одной точке может быть подключено несколько линий. В этой задаче мы не учитываем потери и прочие параметры.
Входной формат: список пар целых чисел, где каждая пара — координаты соответствующей точки подключения.
Выходной формат: список пар целых чисел, где каждая пара описывает отдельную линию между точками подключения, а число в этой паре означает порядковый номер точки во входном списке (нумерация с 0).