FRAKTAL - konkurs programistyczny

Od pewnego czasu trwa modernizacja dróg w południowej Bajtocji. Pan Andrzej Inżynierski zaproponował algorytm, według którego będzie budowana autostrada w tym kraju. Będzie ona ciągnęła się przez wszystkie miasta według algorytmu:

• zaczynamy od miasta, którego współrzędne podano jako pierwsze
• łączymy je z najbliższym, do którego jeszcze nie ma połączenia. Jeśli jest kilka takich, wybieramy to, którego współrzędna x jest najmniejsza, jeśli i takich jest kilka, wybieramy to, którego współrzędna y jest najmniejsza. 

Gwarantuje się, że miasta mają różne pozycje.

Jak pewnie zauważyłeś, niektóre autostrady mogą się przecinać. Aby uniknąć kolizjii w punkcie przecięcia się autostrady budujemy wiadukt.

Warunki postawienia wiaduktu:

• wiadukt stawiamy tylko wtedy, gdy dwie drogi przecinają się pod kątem większym od 0 stopni (nie nakładają się na siebie równolegle w dowolnym odcinku),
• wiaduktu nie stawiamy, gdy trafia on na współrzędne miasta,
• jeśli więcej dróg przecina się w tym samym punkcie, dla każdej z nich stawiamy wiadukt,

Twoim zadaniem jest obliczenie długości autostrady oraz wyznaczenie liczby wiaduktów.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę miast (n < 5001).

W kolejnych n wierszach po dwie liczby całkowite x i y będące współrzędnymi miast (|x| < 10001, |y| < 10001).

Wyjście

Dwa wiersze. W pierwszym wierszu długość sumaryczna autostrad zaokrąglona do dwóch miejsc po przecinku. W drugim liczba wiaduktów.

Przykład

Wejście:
5
0 0
4 0
4 2
3 -4
-3 -5

Wyjście:
18.17
1