问题
猎鹰 是一种使用猛禽的狩猎方式。一日三 猎鹰者 (做猎鹰的人)决定进行下一场比赛。
有 N 二维平面上的检查点, i_{th} 检查点存在于坐标为 (x_i,y_i)。三个猎鹰人位于坐标为 (x_a, y_a), (x_b, y_b), (x_c, y_c)。他们每人都有一只鸟。一开始,每只鸟都和主人待在一起,因此它的坐标与主人的坐标相同。
比赛开始时, 3 鸟类将开始移动。本次比赛的目的是让所有检查点至少由一只鸟通过,并使三只鸟的移动距离之和最小。在这种情况下,距离是指欧几里德距离。两点之间的距离 (x_s, y_s) 和 (x_t, y_t) is \sqrt{(x_s - x_t)^2 + (y_s - y_t)^2}.
检查点可以按任意顺序通过。对于鸟来说,可以不通过任何检查点或通过所有检查点。此外,同一检查点可以多次通过。此外,假设每只鸟都可以选择最佳的移动方式。
将给出所有检查点和三名猎鹰人的坐标。请求三只鸟移动距离之和的最小值。
输入
输入将由以下格式的标准输入给出
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
- 对于第一行, 将给出 N (1 ≦ N ≦ 18) 。
- 从第二行开始,有 N 附加线,每条线都会给出检查点的坐标。 i_{th} 行,整数 x_i(-10,000≦x_i≦10,000), y_i(-10,000≦y_i≦10,000) 将除以空格。
- 对于 (N+2)_{th} 线, x_a(-10,000≦x_a≦10,000)、y_a(-10,000≦y_a≦10,000) 将除以空格。
- 对于 (N+3)_{th} 线, x_b(-10,000≦x_b≦10,000)、y_b(-10,000≦y_b≦10,000) 将除以空格。
- 对于 (N+4)_{th} 线 x_c(-10,000≦x_c≦10,000)、y_c(-10,000≦y_c≦10,000) 将除以空格。
此外,所有坐标都彼此不同。
换句话说,如果 i \neq j 然后 (x_i, y_i) \neq (x_j, y_j).
此外,对于每个 i (1 ≦ i ≦ N), (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) 将保持。此外, (x_a, y_a) \neq (x_b, y_b), (x_b, y_b) \neq (x_c, y_c) 和 (x_c, y_c) \neq (x_a, y_a) 将保持。
输出
输出当一行中至少一只鸟通过所有检查点时,三只鸟移动距离之和的最小值。
如果绝对误差或相对误差满足,则输出可接受 10^{-6} 或更少。
在输出末尾打印换行符。
输入示例 1
3 1 1 102 98 197 -197 0 0 100 100 200 -200
输出示例 1
8.485281374239
- 如果从 (x_a, y_a) 经过第一个检查点,移动距离为 \sqrt{2}.
- 如果从 (x_b, y_b) 经过第二个检查点,移动距离为 2\sqrt{2}.
- 如果从 (x_c, y_c) 经过第三个检查点,移动距离为 3\sqrt{2}.
因此,通过移动 6\sqrt{2}所有检查点将至少通过一次。
输入示例 2
3 1 3 2 1 0 -2 0 0 -500 0 0 1000
输出示例 2
7.841619252964
如果从 (x_a, y_a) 经过第三个检查点,再经过第二个检查点,再经过第一个检查点,总共移动距离为 2 + \sqrt{13} + \sqrt{5}.
输入示例3
6 3 7 1 10 -2 -5 -3 4 0 2 6 6 -3 9 0 4 1 1
输出示例 3
22.585258012904