<ПРЕД Задача:
СЛЕД>
Задачу решили 299 пользователей: ...
UserDateAttemptTimeCMSC
army21 aug 2009C++400.60202 
TheVice03 mar 2007Kylix602.69214 
Tulegenov_Amir17 mar 2007Kylix1902.87214 
Quazar09 may 2010FPC102.59215 
olesheg05 jan 2011FPC202.60215 
Zaurbek_I13 mar 2007FPC1202.63215 
Zaurbek_I13 mar 2007FPC1302.63215 
Ivan_KBTU05 dec 2009C++203.54215 
TheVice13 mar 2007Kylix802.54216 
Zaurbek_I28 feb 2007Kylix1102.55216 
Tulegenov_Amir11 mar 2007Kylix1702.10218 
Tulegenov_Amir11 mar 2007Kylix1802.10218 
nt_d228 oct 2006FPC2600.20221 
D.S10 mar 2004FPC3?.??222 
SerikBeketayev16 mar 2007Kylix1302.50223 
Языки
C++
171
FPC
87
Kylix
21
C
18
Java
9
Python
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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

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 = 18.232.51.69