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 COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET

ukryj komentarze
2016-11-20 10:18:12 Marcin Kasprowicz
Tak
2016-11-20 09:59:07 Grzegorz Spryszyñski
Po połączeniu jednego miasta z drugim, idziemy do tego drugiego miasta i powtarzamy całą procedurę?
W przykładzie kolejność to będzie (0,0), (4,0), (4,2), (3,-4), (-3,-5)? A współrzędne jedynego wiaduktu (3.25, 0)?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.