AT_code_festival_2015_okinawa_f Falconry

在一个二维平面上有 $N$ 个检查点，第 $i$ 个检查点的坐标为 $(x_i, y_i)$。有三个驯鹰者分别站在坐标 $(x_a, y_a)$、$(x_b, y_b)$ 和 $(x_c, y_c)$ 的位置，每位驯鹰者各持有一只鸟。比赛开始时，每只鸟都停留在其主人的位置。 比赛的目的是让所有检查点至少被一只鸟经过一次，同时要尽可能缩短三只鸟的总移动距离。移动距离是使用欧几里得距离计算的，也就是两个点 $(x_s, y_s)$ 和 $(x_t, y_t)$ 之间的距离为 $\sqrt{(x_s - x_t)^2 + (y_s - y_t)^2}$。 这些检查点可以按照任何顺序经过。一只鸟可以选择不经过任何检查点，也可以遍历所有检查点。同一个检查点可以被多次经过。假设每只鸟都能找到最短的路线。 现在给出所有检查点和三个驯鹰者的坐标，请计算三只鸟移动的最小总距离。

输入通过标准输入给出，格式如下： - 第一行包含一个整数 $N$，表示检查点的数量 ($1 \leq N \leq 18$)。 - 接下来的 $N$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个检查点的坐标，$-10,000 \leq x_i, y_i \leq 10,000$。 - 第 $N+2$ 行包含两个整数 $x_a$ 和 $y_a$，表示第一个驯鹰者的位置。 - 第 $N+3$ 行包含两个整数 $x_b$ 和 $y_b$，表示第二个驯鹰者的位置。 - 第 $N+4$ 行包含两个整数 $x_c$ 和 $y_c$，表示第三个驯鹰者的位置。 所有的坐标值各不相同。具体来说，若 $i \neq j$，则 $(x_i, y_i) \neq (x_j, y_j)$。同时，对于每个检查点 $(x_i, y_i)$，它不会与驯鹰者的位置重合，即 $(x_i, y_i) \neq (x_a, y_a)$、$(x_i, y_i) \neq (x_b, y_b)$、$(x_i, y_i) \neq (x_c, y_c)$。此外，不同驯鹰者的位置也不会重合。

输出一个数字，表示三只鸟移动的最小总距离。结果的绝对误差或相对误差不超过 $10^{-6}$ 即可接受。 输出结果以换行结尾。 **本翻译由 AI 自动生成**

### 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} $.