103345: [Atcoder]ABC334 F - Christmas Present 2

Problem Statement

There is a town represented as an $xy$-plane, where Santa lives, along with $N$ children numbered $1$ to $N$. Santa's house is at coordinates $(S_X,S_Y)$, and the house of child $i\ (1\leq i\leq N)$ is at $(X_i,Y_i)$.

Santa wants to deliver one present to each of the $N$ children in numerical order. To deliver a present to child $i$, Santa must visit the house of child $i$ with at least one present in hand. However, Santa can only carry up to $K$ presents at a time, and he must return to his own house to replenish presents (there are enough presents at Santa's house).

Find the minimum distance Santa must travel to leave his house, deliver presents to all $N$ children, and return to his house.

Constraints

• $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)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$
$S_X$ $S_Y$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

Output

Print the minimum distance Santa must travel. The output will be considered correct if the absolute or relative error from the true value is at most $10^{−6}$.

Sample Input 1

3 2
1 1
3 1
1 2
3 2

Sample Output 1

9.236067977499790

In the figure above, the red circle represents Santa's house, and the circles with numbers represent the houses of the children with those numbers.

Consider Santa acting as follows:

1. Leave his house with two presents.
2. Go to child $1$'s house and deliver a present.
3. Return to his house and replenish one present.
4. Go to child $2$'s house and deliver a present.
5. Go to child $3$'s house and deliver a present.
6. Return to his house.

In this case, Santa travels the distance of $2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots$, which is the minimum.

Sample Input 2

2 1
0 1
-1 1
1 1

Sample Output 2

4.000000000000000

Sample Input 3

8 3
735867677 193944314
586260100 -192321079
95834122 802780784
418379342 -790013317
-445130206 189801569
-354684803 -49687658
-204491568 -840249197
853829789 470958158
-751917965 762048217

Sample Output 3

11347715738.116592407226562

问题描述

有一个城镇，可以用一个xy坐标系表示，圣诞老人和他的N个孩子住在那里，编号为1到N。 圣诞老人的房子在坐标(S_X,S_Y)，而第i个孩子（1≤i≤N）的房子在(X_i,Y_i)。

圣诞老人想按顺序给每个孩子送一份礼物。 为了给第i个孩子送礼物，圣诞老人必须带着至少一份礼物去孩子家。 然而，圣诞老人一次只能携带最多K份礼物，他必须返回自己的房子补充礼物（圣诞老人家有足够的礼物）。

找出圣诞老人必须走的最短距离，离开他的房子，给所有N个孩子送礼物，然后返回他的房子。

约束条件

• 1≤K≤N≤2×10^5
• -10^9≤S_X,S_Y,X_i,Y_i≤10^9
• (S_X,S_Y)≠(X_i,Y_i)
• (X_i,Y_i)≠(X_j,Y_j) (i≠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