圣诞礼物 2

题目描述

有一座用 $xy$ 平面表示的城镇,圣诞老人居住于此,城镇里还有编号为 $1$ 到 $N$ 的 $N$ 个孩子。 圣诞老人的房子位于坐标 $(S_X,S_Y)$,孩子 $i\ (1\leq i\leq N)$ 的房子位于 $(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}$ 时,答案被视为正确。

样例

3 2
1 1
3 1
1 2
3 2

9.236067977499790

考虑圣诞老人如下行动:

带着两份礼物离开家。

前往孩子 1 的家并送出一份礼物。

回到自己的家补充一份礼物。

前往孩子 2 的家送出一份礼物。

前往孩子 3 的家送出一份礼物。

回到自己的家。

这种情况下,圣诞老人移动的距离为 $2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\ldots$,这是最小值。

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