分数: 550 点
问题陈述
有一个城镇表示为 xy- 飞机,圣诞老人居住的地方,还有 N 儿童编号 1 to N。 圣诞老人的房子位于坐标处 (S_X,S_Y),还有孩子的房子 i\ (1\leq i\leq N) 位于 (X_i,Y_i).
圣诞老人想给每个人送一份礼物 N 儿童 按数字顺序。 给孩子送礼物 i, 圣诞老人必须拜访孩子的家 i 手中至少有一份。 然而,圣诞老人最多只能携带 K 一次礼物,他必须返回自己的房子补充礼物(圣诞老人家里有足够的礼物)。
找出圣诞老人离开家所需的最短距离,向所有人分发礼物 N 孩子们,回到他家。
约束
- 1\leq K\leq N \leq 2\times 10^5
- -10^9\leq S_X,S_Y,X_i,Y_i \leq 10^9
- (S_X,S_Y)\neq (X_i,Y_i)
- (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K S_X S_Y X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
输出
打印圣诞老人必须行驶的最短距离。 如果与真实值的绝对或相对误差最多为,则输出将被认为是正确的 10^{−6}.
示例输入 1
3 2 1 1 3 1 1 2 3 2
示例输出 1
9.236067977499790

上图中,红色圆圈代表圣诞老人的房子,带有数字的圆圈代表具有该数字的孩子的房子。
考虑圣诞老人的行为如下:
- 带着两件礼物离开他的家。
- 转到子项 1的房子并送礼物。
- 回到他家并补充一份礼物。
- 转到子项 2的房子并送礼物。
- 转到子项 3的房子并送礼物。
- 回到他家。
在这种情况下,圣诞老人走了的距离 2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots,这是最小值。
示例输入 2
2 1 0 1 -1 1 1 1
示例输出 2
4.000000000000000
示例输入 3
8 3 735867677 193944314 586260100 -192321079 95834122 802780784 418379342 -790013317 -445130206 189801569 -354684803 -49687658 -204491568 -840249197 853829789 470958158 -751917965 762048217
示例输出 3
11347715738.116592407226562