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.|

AL_15_09 - Plamy

Jaś ma już dosyć bałaganu w swoim pokoju i podjął twarde postanowienie o doprowadzeniu go do porządku. Jako, że każdy wielki wyczyn zaczyna się od drobnego kroku - nasz bohater postanowił w pierwszej kolejności zadbać o czystość podłogi. Od ostatniego sprzątania minęło już wiele konkursów programistycznych, tak więc jej stan pozostawia sporo do życzenia. Liczba plam i zabrudzeń przyprawiłaby każdego o ból głowy, ale Jaś ma głowę nie od parady, tak więc błyskawicznie znalazł rozwiązanie! Sprzątanie zacznie od... napisania programu :-)

Jaś zaznaczył na mapie pokoju współrzędne wszystkich n-1 plam na podłodze, a także miejsce, w którym znajduje się mop. Nasz bohater chciałby, aby program wyliczył najkrótszą trasę jaką musi pokonać, żeby zmyć wszystkie zabrudzenia. Jaś zostawił mopa pod ścianą znajdującą się z lewej strony pokoju, a zatem jego lokalizacji odpowiada punkt o minimalnej wartości współrzędnej x. Nasz bohater zauważył również, że na narysowanej mapie każdy z punktów ma niepowtarzalną wartość współrzędnej x. Jaś, jak na programistę przystało, nie ma zbyt dużego doświadczenia w sprzątaniu, tak więc postanowił wykonać całe zadanie w dość niecodzienny sposób. Chłopiec zamierza posprzątać całą podłogę idąc od lewej strony pokoju do prawej, następnie zawróci (dokładnie jeden raz) i ponownie dotrze do miejsca, z którego rozpoczął. Musi tam wrócić, aby odłożyć mopa na swoje miejsce. Jaś może czyścić plamy zarówno idąc od lewej strony do prawej jak i wracając.

Nie chcielibyśmy wysuwać żadnych insynuacji odnośnie czystości podłogi w Twoim pokoju, uważamy jednak, że taki program zawsze warto mieć!

Wejście

W pierwszej linii wejścia znajduje jedna liczba całkowita n (2 ≤ n ≤ 1000) określająca liczbę punktów zaznaczonych na mapie Jasia. W kolejnych n liniach znajdują się po dwie liczby całkowite x, y (0 ≤ x, y ≤ 20000) określające współrzędne punktów. Punkty odpowiadają lokalizacji n-1 plam oraz mopa.

Wyjście

Na wyjściu wypisz długość szukanej ścieżki z dokładnością do dwóch miejsc po przecinku.

Przykład

Wejście

4
5 1
2 0
0 1
3 2

Wyjście

10.80

Dodane przez:Maciej Boniecki
Data dodania:2014-03-29
Limit czasu wykonania programu:0.100s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

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