粘菌コンピュータというものがある。 ある種の粘菌には「餌を求め、餌と餌の最短距離をつなぐ形に変形する」 という性質がある。 これを利用し、餌を「入力」、形を「出力」とみなして コンピュータとして利用することができる。
今、二次元平面上に1つの粘菌の拠点とN個の餌が存在する。それぞれの餌には1からNまでの異なる番号が与えられ、拠点には番号0が与えられている。 この粘菌はある餌を食べるために、その餌と最も近い拠点の最短距離を結ぶ管状に 成長し、食べた位置に新たに拠点を形成する。 新たに形成した拠点は拠点を形成する直前に食べた餌と同じ番号を持つ。 粘菌は拠点以外の場所から成長することはできない。 以降では、拠点と餌を二次元平面上の点、管状に成長した粘菌を複数の線分として考える。
すべての拠点と線分からなる構造を粘菌網と呼ぶ。 粘菌は1つの餌を食べるために次のような操作を繰り返す。
この粘菌は生きるために必要な栄養を取るのにM個の餌を食べる必要がある。 粘菌がM個の餌を食べるまでに引いたすべての線分の長さの合計を求めよ。 また、出力する値は0.0001以下の誤差を含んでいても良い。
以下の図では入力例2の粘菌の様子を示している。
N M X Y px_1 py_1 ... px_n py_n
1行目には餌の数N(1 \≤ N \≤ 5,000)、食べる餌の個数M (1 \≤ M \≤ N)、番号0の拠点の座標X, Y(−5,000 \≤ X, Y \≤ 5,000)が整数値で与えられる。続くN行には番号順に餌の座標px_i, py_i(1 \≤ i \≤ N)が整数値で与えられる。(−5,000 \≤ px_i, py_i \≤ 5,000) また、番号が異なる餌は異なる座標に存在し、それぞれの餌と番号0の拠点の座標は異なる。
成長した距離の合計を1行で出力せよ。また、出力する値は0.0001以下の誤差を含んでいても良い。
2 2 0 0 3 3 4 0
7.16227766017
最初は番号1の餌と拠点の距離が $3\sqrt{2}$ と番号2の餌と拠点の距離が4なので 番号2の餌が選ばれる。その後番号1の餌と粘菌網との距離が3になり、番号1の餌が選ばれる。
4 4 1 3 3 3 2 1 3 1 1 1
6.2360679775
図のように餌1、2、4、3の順に粘菌は餌を食べていく
16 15 -4077 763 -2480 2841 -2908 -1096 676 -4080 -4988 -2634 3004 -1360 -2272 1773 -4344 -3631 -355 4426 -3740 3634 -3330 2191 -3423 -2999 -3438 2281 4754 -1500 -3440 -3873 -2089 -3419 1426 2793
25349.9626798834