← 返回题目列表

AtCoder · code_festival_2015_okinawa_f

F. 猎鹰

中文机器翻译题面 查看原题

问题

猎鹰 是一种使用猛禽的狩猎方式。一日三 猎鹰者 (做猎鹰的人)决定进行下一场比赛。

有 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