Score : $550$ points

问题描述

在一个以 $xy$-坐标系表示的城镇中，圣诞老人和编号从 $1$ 到 $N$ 的 $N$ 个孩子居住在一起。圣诞老人的房子位于坐标 $(S_X,S_Y)$，而第 $i$（$1\leq i\leq N$）个孩子的房子位于坐标 $(X_i,Y_i)$。

圣诞老人希望按照数值顺序给这 $N$ 个孩子每人送一个礼物。为了给第 $i$ 个孩子送礼物，圣诞老人必须至少携带一份礼物前往该孩子的房子。但是，圣诞老人每次最多只能携带 $K$ 份礼物，并且在礼物用完后他必须返回自己的房子补充礼物（圣诞老人的房子里有足够的礼物）。

请计算圣诞老人从自己家出发，给所有 $N$ 个孩子送出礼物并返回自己家所需的最短距离。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:22:14