Problem S
Hiding Chickens
“Weeeee,” says the fox after breaking in to the roost and killing all the chickens. Then he realizes that he has killed way more chickens then he can eat right now and hence he decides to hide them in already existing hiding spots nearby. The fox can only carry two hens at a time and every hiding spot can fit at most one. As he is already tired after all the killing, he wants you to compute the minimum distance he has to walk to hide all of the dead chickens.
Input
The first line of input gives the position of the roost as two real numbers $x$ and $y$ on a single line. The next line contains an integer $1 \leq N \leq 20$, giving the number of hiding spots and dead chickens. Then follow $N$ lines, each line consisting of two real numbers giving the coordinates of a hiding spot. All coordinate values are between $0$ and $1\, 000$ and given with $6$-digit precision.
Output
A single line with a floating point number, the minimum distance the fox has to walk to hide all the chickens. Any answer with an error of at most $10^{-6}$ will be judged as correct.
Sample Input 1 | Sample Output 1 |
---|---|
10.000000 20.123456 1 13.141593 20.123456 |
3.141593 |
Sample Input 2 | Sample Output 2 |
---|---|
5.000000 5.000000 4 2.000000 9.000000 14.000000 17.000000 6.500000 3.000000 14.000000 18.500000 |
31.500000 |