«Добытчик алмазов» — игра, похожая на «Добытчик золота», но в этой игре \(n\) шахтеров, а не \(1\).
Шахта может быть представлена как плоскость. Будем рассматривать \(n\) шахтеров как \(n\) точек, расположенных на оси y. В шахте расположены \(n\) алмазов, будем рассматривать их как \(n\) точек на оси x. По каким-то причинам ни шахтеры, ни алмазы не могут быть расположены в начале координат (точке \((0, 0)\)).
Каждый шахтер должен добыть ровно один алмаз. У каждого шахтера есть крюк, с помощью которого он может достать алмаз. Если шахтер, находящийся в точке \((a,b)\) использует свой крюк для добычи алмаза, расположенного в точке \((c,d)\), он потратит \(\sqrt{(a-c)^2+(b-d)^2}\) (расстояние между точками) единиц энергии. Шахтеры не могут перемещаться и помогать друг другу.
Цель игры — распределить алмазы по шахтерам так, чтобы минимизировать сумму затраченной энергии. Сможете ли вы найти этот возможный минимум?
Выходные данные
Для каждого набора входных данных выведите одно вещественное число — минимально возможную сумму затраченных энергий.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит \(10^{-9}\).
Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет зачтен, если и только если \(\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}\).
Примечание
В первом примере есть два шахтера в точках \((0,1)\) и \((0,-1)\), а алмазы расположены в точках \((1,0)\) и \((-2,0)\). Если распределить алмазы по шахтерам, как показано на рисунке, то потратится \(\sqrt2 + \sqrt5\) единиц энергии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
0 1
1 0
0 -1
-2 0
4
1 0
3 0
-5 0
6 0
0 3
0 1
0 2
0 4
5
3 0
0 4
0 -3
4 0
2 0
1 0
-3 0
0 -10
0 -2
0 -10
|
3.650281539872885
18.061819283610362
32.052255376143336
|