Codah ClubВежбај. Испрати. Напредувај.
Најави се
Македонски
#00042E

ThePut

You are given n points in plane, which you should insert in set P, in given order. At the beginning the set P consists of only one point. In each of the next n steps, take one of the remaining points t (in given order) and draw the segment joining t with one of the point that belongs to set P. After this, point t becomes part of the set P.


The goal is that after n steps we get a path - open broken line of minimum length (the length of the line is the sum of the lengths of all segments which are part of that line). You should write the minimum length.



Input The first line of standard input contains two integers xs and ys - coordinates of the initial point in [

].The next line contains one positive integer n (1 <= n <= 2.000), number of points. Each of the next n rows contains two integers - coordinates of [i]-th point. Points are given in order of which should be inserted in the set P. All coordinates does not exceed 10.000 by absolute value.



OutputIn first and only line of standard output write minimal length of the path. Your solution will be considered correct if it differs from official by less then 0.001. Your solution should have at least 5 digits after decimal point.



Input:
0 0
3
4 0
1 3
1 0
Output:
9.24264


[p]Path with minimal length is (1, 0) - (0, 0) - (4, 0) - (1, 3). Notice that path can be self-intersecting.

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.