Корневое дерево — это ориентированный ациклический граф, в котором есть одна вершина (корень), из которой существует ровно один путь до любой другой вершины.
Корневое дерево называется бинарным, если каждая вершина имеет не более двух исходящих дуг.
Когда бинарное дерево рисуют на плоскости, все дуги должны быть направлены сверху вниз. То есть для каждой дуги из u в v должно выполняться: yu > yv.
Вам даны координаты всех вершин дерева. Ваша задача — соединить эти вершины дугами так, чтобы получилось бинарное корневое дерево, и суммарная длина дуг была минимальна. Все дуги построенного дерева должны быть направлены сверху вниз.
Выходные данные
Если невозможно построить бинарное дерево на данных точках, выведите «-1». Иначе выведите одно вещественное число — суммарную длину дуг в минимальном бинарном дереве. Ответ будет засчитан, если абсолютная или относительная погрешность не превосходит 10 - 6.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 0
1 0
2 1
|
3.650281539872885
|
|
2
|
4
0 0
1 0
2 1
2 0
|
-1
|