Легенда

Прогресс не стоит на месте, в одном микрорайоне потребовалось заменить устаревшую систему ЛЭП на более надёжную. Но энергетика связана с ресурсами, а ресурсы нужно расходовать бережно.

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

Входной формат: список пар целых чисел, где каждая пара — координаты соответствующей точки подключения.

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

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


Last modified: Tuesday, 15 June 2021, 9:33 AM