Задача №112684. Плюканские авиалинии
Вы не поверите, но на Плюке существуют города. И даже целые огромные торговые центры в них! Передвигаться между ними, естественно, лучше всего на пепелацах. Во-первых, это быстро, во-вторых, меньше вероятность столкнуться с патрулём, которые охотно отберут все имеющиеся в наличии чатлы.
Для тех, у кого нет своего пепелаца, существуют пепелац-такси, которыми можно воспользоваться, чтобы попасть в другой город. Каждое пепелац-такси имеет чёткий маршрут. Маршрут может включать в себя несколько (иногда один) плюканских городов, между которыми пепелац летает: из первого во второй, из второго в третий и так далее. Между городами пепелацы летают исключительно по прямой. Для того, чтобы пилоты не заблудились, на Плюке принята единая декартова координатная система, и для каждого города известны его координаты на плоскости. Координаты города - это целые неотрицательные числа в диапазоне от 0 до 1000. Пепелац-такси может лететь из города \(А\) с координатами (\(x_a\), \(y_a\)) в город \(B\) (\(x_b\), \(y_b\)) только тогда, когда \(y_a\) > \(y_b\). Это приводит ко многим проблемам, например, улетев куда-нибудь на таком такси, вернуться обратно на нём уже невозможно. Но это - мелочи по сравнению с главной проблемой Плюка.
А главная проблема Плюка - нехватка пепелацев и дороговизна топлива для них - луца. По этой причине плюканские власти решили разработать новую схему маршрутов пепелац-такси. По ней каждый город должен принадлежать не более чем одному маршруту. При этом суммарное количество маршрутов и отдельно стоящих городов должно быть минимальным, а из всех таких вариантов нужно выбрать тот, в котором суммарная длина всех маршрутов минимальна. Расстояние между городами определяется обычным образом как декартово расстояние между двумя точками, а длина маршрута - сумма длин перелётов в нём.
Ваша задача - зная расположение городов на Плюке вывести минимальное возможное количество маршрутов пепелац-такси в новой схеме, а также минимально возможную суммарную длину маршрутов среди всех таких схем.
На первой строке входного файла дано число \(N\) (1 ≤ \(N\) ≤ 100) - число городов на Плюке. Последующие \(N\) строк содержат по два целых числа \(x\), \(y\) (0 ≤ \(x\), \(y\) ≤ 1000) - координаты плюканских городов.
На первой строке входного файла выведите одно целое число - минимальное суммарное количество маршрутов пепелац-такси и отдельно стоящих городов в новой схеме. На второй строке одно вещественное число с тремя знаками после запятой - минимально возможная суммарная длина этих маршрутов.
2 1 1 2 2
1 1.414
2 1 1 2 1
2 0.000