AT_abc334_f [ABC334F] Christmas Present 2

题目描述

有一个以 $xy$ 平面表示的小镇，镇上住着圣诞老人和 $N$ 个编号为 $1$ 到 $N$ 的孩子。圣诞老人的家的坐标为 $(S_X, S_Y)$，第 $i$ 个孩子的家的坐标为 $(X_i, Y_i)$。

圣诞老人想要按照编号顺序，依次给 $N$ 个孩子每人送一个礼物。为了给第 $i$ 个孩子送礼物，圣诞老人必须在手中至少有一个礼物的情况下前往第 $i$ 个孩子的家。然而，圣诞老人一次最多只能携带 $K$ 个礼物，如果需要补充礼物，必须返回自己的家（圣诞老人的家中有足够多的礼物）。

请你求出圣诞老人从自己家出发，给所有 $N$ 个孩子送完礼物后再回到自己家的最小移动距离。

输入格式

输入以以下格式从标准输入读入。

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

输出格式

输出圣诞老人移动的最小距离。若输出值与真实值的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

输入输出样例 #1

输入 #1

3 2
1 1
3 1
1 2
3 2

输出 #1

9.236067977499790

输入输出样例 #2

输入 #2

2 1
0 1
-1 1
1 1

输出 #2

4.000000000000000

输入输出样例 #3

输入 #3

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

输出 #3

11347715738.116592407226562

说明/提示

限制条件

• $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)$
• 所有输入均为整数

样例解释 1

在上图中，红色圆点表示圣诞老人的家，带有数字的圆点表示对应编号的孩子的家。考虑圣诞老人按如下方式行动：

1. 从家中带 $2$ 个礼物出发。
2. 前往第 $1$ 个孩子家，送出 $1$ 个礼物。
3. 返回家中补充 $1$ 个礼物。
4. 前往第 $2$ 个孩子家，送出 $1$ 个礼物。
5. 前往第 $3$ 个孩子家，送出 $1$ 个礼物。
6. 返回家中。

此时，圣诞老人移动的总距离为 $2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots$，这是最小值。

由 ChatGPT 4.1 翻译