Блок задач

3. Структуры данных

Темы
Сложность 5

Задача «Построение минимального остовного дерева»

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

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

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

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

Пример:

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

Задача

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

Основной алгоритм необходимо реализовать в виде отдельной функции примерно следующего вида:

typedef std::pair<int, int> point_t; // точка с координатами на плоскости (может быть реализовано иначе)
typedef std::pair<size_t, size_t> edge_t; // ребро между точками №... и №...

std::vector<edge_t> build(const std::vector<point_t> & points);

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

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

<pont_id1> - <pont_id2>
...

Пример:

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

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

Для основной функции build должен быть создан набор тестов, проверяющих корректность вычислений на наборе примеров, а также проверяющий поведение в случае некорректных исходных данных. Приветствуется также тестирование функций ввода/вывода.