Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_06_14 - Wiadukty

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

Dodane przez:Marcin Kasprowicz
Data dodania:2016-10-17
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.