Задание № 3259

Студент

Лисихина Екатерина

Задача

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

Состояние

Завершено

Баллов

4

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

09.04.2021, 07:02

Завершено

31.05.2021, 02:05

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

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

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

<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.

Примечания

Есть небольшие косяки

Действия