Задание № 5679

Студент

Бороздин Павел

Задача

Построение минимального остовного дерева

Состояние

Завершено

Баллов

5

Дедлайн
18 апреля
Назначено

10.04.2024, 04:34

Завершено

10.04.2024, 12:11

Построить минимальное остовное дерево из точек на плоскости.

Входные данные

Текстовый файл с набором пар координат на плоскости.

<pont_id1>, <x1>, <y1>
<pont_id2>, <x2>, <y2>
...

Пример:

1, 7, 5
2, 3, -11
3, 2, -2
4, -1, -8
5, 14, -14

Файл может содержать пустые и невалидные строки. Программа должна корректно это обрабатывать.

Задача

Необходимо связать множестве точек на плоскости таким образом, чтобы сумма длин рёбер была минимальна. Для решения задачи необходимо использовать Алгоритм Крускала. Длинна ребра между любой парой точек вычисляется стандартно, как геометрическое расстояние между точками.

Выходные данные

Текстовый файл, описывающий ребра построенного дерева:

<pont_id1> - <pont_id2>
...

Пример:

1 - 3
2 - 4
2 - 5
3 - 4

Тестирование

Для всех разработанных модулей должны быть созданы наборы unit тестов. Функций ввода/вывода нужно тестировать с помощью std::stringstream.

Действия