← 返回题目列表

AtCoder · abc334_f

I. 圣诞礼物2

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

分数: 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. 转到子项 1的房子并送礼物。
  3. 回到他家并补充一份礼物。
  4. 转到子项 2的房子并送礼物。
  5. 转到子项 3的房子并送礼物。
  6. 回到他家。

在这种情况下,圣诞老人走了的距离 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