Codah ClubExersează. Trimite. Progresează.
Autentificare
Română
#00042E

ThePut

Dat je skup P koji se na početku sastoji iz jedne tačke i niz od n tačaka. U svakom od n narednih koraka, uzimamo tačke iz niza (redom kojim su date u nizu) i crtamo duž od uzete tačke do neke tacke iz skupa P, pri čemu uzeta tacka postaje deo skupa P. Cilj je na kraju dobiti put - otvorenu izlomljenu liniju minimalne dužine (dužina linije je zbir dužina svih duži te linije). Štampati minimalnu duzinu.



Input U prvom redu standarnog ulaza nalaze se dva cela broja xs i ys, koji predstavljaju koordinate početne tačke skupa [

]. U sledećem redu se nalazi prirodan broj n <= 2.000, broj tačaka niza. U narednih n redova se nalaze po dva cela broja - koordinate odgovarajuce tačke. Tačke su date u redosledu kojim se uzimaju iz niza. Koordinate svake tačke ne prelaze 10.000 po apsolutnoj vrednosti.



Output U prvom i jedinom redu standardnog izlaza ispisati minimalnu dužinu puta. Rešenje će se smatrati tačnim ako se od pravog minimuma razlikuje za manje od 0.001 po apsolutnoj vrednosti. Rešenje štampati na bar 5 decimale.



Input:

0 0
3
4 0
1 3
1 0

Output:

9.24264


[p] Put sa minimalnom dužinom je (1, 0) - (0, 0) - (4, 0) - (1, 3). Primetimo da put moze imati samopresecanja.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.