Задание № 2424

Студент

Еркович Степан

Задача

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

Состояние

Завершено

Баллов

5

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

05.04.2020, 10:19

Завершено

25.05.2020, 09:19

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

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

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

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

Действия