<ПРЕД Задача:
СЛЕД>
Задачу решили 299 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Наилучшее разбиение

Time limit = 4 секунд

Дано четное количество точек на плоскости. Нужно их ВСЕ разбить на пары (каждая точка принадлежит ровно одной паре). Каждая пара образует отрезок.

Найдите такое разбиение, при котором сумма длин всех отрезков была минимальна.

Вывести нужно суммарную длину отрезков с точностью до 3-х знаков после точки.

Вход общее число точек N, 2 ≤ N ≤ 20
координата-X координата-Y
координата-X координата-Y
...
Все координаты действительные числа по модулю меньше 100000.

Выход Минимальная суммарная длина отрезков.

Вход#1
4
0.0 0.0
0.0 1.0
2.0 0.0
2.0 1.0
Выход#1
2.0

Автор:
Ворожцов Артем
4 октября 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 3.226.248.180