AT_code_festival_2015_okinawa_f Falconry

[problemUrl]: https://atcoder.jp/contests/code-festival-2015-okinawa-open/tasks/code_festival_2015_okinawa_f

Inputs will be given by standard input in following format > $ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ : $ x_N $ $ y_N $ $ x_a $ $ y_a $ $ x_b $ $ y_b $ $ x_c $ $ y_c $ - For the first line, $ N\ (1\ ≦\ N\ ≦\ 18) $ will be given. - From the second line, there are $ N $ additional lines, for each line the coordinate of a checkpoint will be given. For the $ i_{th} $ line, integer $ x_i(-10,000≦x_i≦10,000) $, $ y_i(-10,000≦y_i≦10,000) $ will be given divided by a space. - For the $ (N+2)_{th} $ line, $ x_a(-10,000≦x_a≦10,000) $、$ y_a(-10,000≦y_a≦10,000) $ will be given divided by a space. - For the $ (N+3)_{th} $ line, $ x_b(-10,000≦x_b≦10,000) $、$ y_b(-10,000≦y_b≦10,000) $ will be given divided by a space. - For the $ (N+4)_{th} $ line $ x_c(-10,000≦x_c≦10,000) $、$ y_c(-10,000≦y_c≦10,000) $ will be given divided by a space. In addition, all the coordinates are different from each other. In other words, if $ i\ \neq\ j $ then $ (x_i,\ y_i)\ \neq\ (x_j,\ y_j) $. Also, for each $ i\ (1\ ≦\ i\ ≦\ N) $, $ (x_i,\ y_i)\ \neq\ (x_a,\ y_a) $, $ (x_i,\ y_i)\ \neq\ (x_b,\ y_b) $ and $ (x_i,\ y_i)\ \neq\ (x_c,\ y_c) $ will hold. Furthermore, $ (x_a,\ y_a)\ \neq\ (x_b,\ y_b) $, $ (x_b,\ y_b)\ \neq\ (x_c,\ y_c) $ and $ (x_c,\ y_c)\ \neq\ (x_a,\ y_a) $ will hold.

Output the minimum value of the sum of the moving distance of three birds when all the checkpoints have been passed through by at least one bird in one line. The output is acceptable if absolute error or relative error is $ 10^{-6} $ or less. Print a newline at the end of output.

### Problem **Falconry** is a kind of hunting using a bird of prey. One day, three **falconers** (the person who do falconry) decided to carry out the next competition. There are $ N $ checkpoints on a two-dimensional plane, the $ i_{th} $ checkpoint exists on the point of which the coordinate is $ (x_i,y_i) $. The three falconers exist on the points of which the coordinates are $ (x_a,\ y_a) $, $ (x_b,\ y_b) $, $ (x_c,\ y_c) $. Each one of them has one bird. In the beginning, every bird stays with its owner, thus the coordinate of it is the same as that of its owner. When the competition begins, $ 3 $ birds will start to move. The purpose of this competition is to let all the checkpoints to be passed through by one bird at least, and to minimize the sum of the moving distance of the three birds. In this case, distance refers to the Euclidean Distance. The distance between two points $ (x_s,\ y_s) $ and $ (x_t,\ y_t) $ is $ \sqrt{(x_s\ -\ x_t)^2\ +\ (y_s\ -\ y_t)^2} $. Checkpoints can be passed through in any order. For a bird, it is allowed to pass no checkpoint or pass all the checkpoints. Also, the same checkpoint can be passed through more than once. In addition, suppose that each bird can choose the optimal way to move. The coordinates of all the checkpoints and the three falconers will be given. Please find the minimum value of the sum of the moving distance of three birds. ### Sample Explanation 1 \- If the bird that starts from $ (x_a,\ y_a) $ passes through the first checkpoint, the moving distance will be $ \sqrt{2} $. - If the bird that starts from $ (x_b,\ y_b) $ passes through the second checkpoint, the moving distance will be $ 2\sqrt{2} $. - If the bird that starts from $ (x_c,\ y_c) $ passes through the third checkpoint, the moving distance will be $ 3\sqrt{2} $. Hence, by moving $ 6\sqrt{2} $all the checkpoints will be passed through at least once. ### Sample Explanation 2 If the bird that starts from $ (x_a,\ y_a) $ passes the third checkpoint, then passes the second checkpoint, then passes the first checkpoint, the moving distance in total will be $ 2\ +\ \sqrt{13}\ +\ \sqrt{5} $.