Limit pamięci: 4MB
W Wielkim Lesie Bajtockim mieszkają odludkowie. Ich chatki znajdują się w punktach odległych o całkowitą liczbę metrów od środka lasu (zarówno w pionie jak i w poziomie). Odludkowie wbrew nazwie lubią swoje towarzystwo, dlatego chcieliby wyciąć przez las ścieżki (będące odcinkami) między chatkami, tak by z każdej chatki dało się dojść do innej (idąc pewną liczbą ścieżek). Ponieważ odludkowie nie należą do najpracowitszych mieszkańców lasu, chcieliby wyciąć jak najmniej ścieżek. Dodatkowo, ścieżki te nie mogą się przecinać, gdyż wtedy łatwo byłoby pomylić drogę, a odludkowie nie są urodzonymi traperami. Do geniuszy informatycznych również sporo im brakuje, dlatego to właśnie Ciebie poprosili o zaplanowanie tras. Chcieliby się jedynie dowiedzieć jaka będzie suma długości ścieżek. Patrząc na ich smutny los, zlitowałeś się i w trosce o ich zdrowie postanowiłeś zminimalizować tę sumę. Przy okazji, los chciał by żadne trzy chatki nie leżały na jednej linii prostej.
Wejście:
W pierwszej linii wejścia znajduje się jedna liczba naturalna n ( 1 <= n <= 2000) – liczba chatek. W liniach od 2 do n+1 wypisane są po dwie liczby całkowite. W linii i+1 znajdują się liczby całĸowite: ( -1000000000 <= xi,yi <= 1000000000 ) i oznaczają położenie i-tej chatki względem środka lasu – punktu (0,0).
Wyjście:
Na wyjściu ma zostać wypisana dokładnie jedna liczba rzeczywista (wypisana z dokładnie pięcioma miejscami po przecinku) – najmniejsza suma długości najmniejszej liczby nieprzecinających się ścieżek (poza chatkami), łączących ze sobą wszystkie chatki.
Przykład:
Dla wejścia:
3
0 1
1 0
0 0
Wypisujemy wynik:
2.00000