F - Christmas Present 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 550 点

問題文

xy 平面として表される町があり、サンタさんと、1 から N までの番号が付けられた N 人の子供が住んでいます。 サンタさんの家の座標は (S_X,S_Y) であり、子供 i\ (1\leq i\leq N) の家の座標は (X_i,Y_i) です。

サンタさんは、N 人の子供たちに番号順にプレゼントを 1 個ずつ配りたいです。 子供 i にプレゼントを配るためには、プレゼントを 1 個以上持った状態で子供 i の家に行く必要があります。 しかし、サンタさんは同時に K 個までしかプレゼントを持つことができず、プレゼントを補充するためには一旦自分の家に戻る必要があります（サンタさんの家には十分な数のプレゼントがあります）。

サンタさんが自分の家を出発し、N 人の子供たち全員にプレゼントを配って、自分の家まで戻ってくるために移動する距離の最小値を求めてください。

制約

  • 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)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

サンタさんが移動する距離の最小値を出力せよ。 出力は、真の値との絶対誤差または相対誤差が 10^{−6} 以下のとき正解と判定される。

入力例 1

3 2
1 1
3 1
1 2
3 2

出力例 1

9.236067977499790

上図において、赤い丸はサンタさんの家、中に数字が書かれた丸はその番号の子供の家を表しています。

サンタさんが以下のように行動することを考えます。

  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 となり、これが最小です。

入力例 2

2 1
0 1
-1 1
1 1

出力例 2

4.000000000000000

入力例 3

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

出力例 3

11347715738.116592407226562

Score : 550 points

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