Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
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łowego | 50000B |
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 |