Christmas Present 2

题目描述

有一个用 $xy$$-$平面表示的小镇，圣诞老人和编号为 $1$ 到 $N$ 的 $N$ 个孩子住在这个小镇上。 圣诞老人的家位于坐标 $(S_X,S_Y)$，孩子 $i\ (1\leq i\leq N)$ 的家位于 $(X_i,Y_i)$。 圣诞老人想要按照 编号顺序 给每个孩子送一份礼物。 要给孩子 $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}$，则认为输出是正确的。

3 2
1 1
3 1
1 2
3 2

9.236067977499790

2 1
0 1
-1 1
1 1

4.000000000000000

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

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$ 的家并送出一份礼物。 回到他家并补充一份礼物。 去孩子 $2$ 的家并送出一份礼物。 去孩子 $3$ 的家并送出一份礼物。 返回他家。

在这种情况下，圣诞老人行走的距离为 $2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots$，这是最短的距离。

标签: AtCoder|abc334F

来源

AtCoder|abc334F