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

LEMONS - Druty i cytrynki

Jaś lubi się bawić w rózne gry, ale pora przestać gdyż otrzymał dziś rano od mamy zestaw małego Sobolka. Jaś wciągnięty w świat fizyki postanowił poeksperymentować. Sobolek wymyślił ciekawy eksperyment. Polega on na uzyskiwaniu energii z cytryn. Jaś ma więc połączyć n-1 cytryn i żarówkę za pomocą drutu. Sprawa wygląda jednak nieciekawie bo tegoż drutu musi użyć jak najmniej i tu sprawa się komplikuje bo gość kompletnie nie wie jak to zrobić. Pewnie wiesz co masz zrobić więc dokończ obiad i bierz się do roboty.

Wejście

Pierwsza linia wejścia zawiera liczbę n będącą liczbą cytryn i żarówki (0<=n<=1000).

Druga linia wejścia zawiera współrzędne żarówki w postaci x, y (-1000<=x,y<=1000).

Kolejne n-1 linii zawiera współrzędne cytryn w postaci x, y (-1000<=x,y<=1000).

Wyjście

Pierwsza i jedyna linia wejścia zawiera liczbę będącą długością drutu tak, by drut dotykał wszystkich cytryn i żarówki (nie musi zamykać obwodu) i przy okazji by był on jak najkrótszy. Liczba ta ma być liczbą całkowitą (UWAGA: Długość każdego odcinka przedstawiaj jako liczbę całkowitą, tzn. jeśli k=14.94 to [k]=14).

Przykład

Wejście:
10
1 4
2 5
2 1
1 1
3 3
2 8
1 6
2 3
4 1
0 3
Wyjście:
12

Image Hosted by ImageShack.us

Dodane przez:Michael Suchacz
Data dodania:2009-02-25
Limit czasu wykonania programu:0.136s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.