9109: ABC334 —— F - Christmas Present 2
[Creator : ]
Description
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≤i≤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.
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.
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$
$⋮$
$X_N\ Y_N$
$N\ K$
$S_X\ S_Y$
$X_1\ Y_1$
$X_2\ Y_2$
$⋮$
$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}$.
Constraints
$1≤K≤N≤2×10^5$
$-10^9≤S_X,S_Y,X_i,Y_i≤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.
$-10^9≤S_X,S_Y,X_i,Y_i≤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.
Sample 1 Input
3 2
1 1
3 1
1 2
3 2
Sample 1 Output
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:
- Leave his house with two presents.
- Go to child 1's house and deliver a present.
- Return to his house and replenish one present.
- Go to child 2's house and deliver a present.
- Go to child 3's house and deliver a present.
- Return to his house.
Sample 2 Input
2 1
0 1
-1 1
1 1
Sample 2 Output
4.000000000000000
Sample 3 Input
8 3
735867677 193944314
586260100 -192321079
95834122 802780784
418379342 -790013317
-445130206 189801569
-354684803 -49687658
-204491568 -840249197
853829789 470958158
-751917965 762048217
Sample 3 Output
11347715738.116592407226562
HINT
相同题目：ABC334。