Broadcasting(テレビ放送) - joi2012-day2

出力のみの課題 (Output-only task)

JOI 国ではこの度，テレビ放送を開始することになった．

JOI 国には N 戸の家がある．これらすべての家でテレビ放送が見られるようにするため，電波塔を建てる必要がある．

今回 JOI 国の国王は K 本の電波塔を建てることに決めた．

i 番目の電波塔を座標 (X_i,Y_i) に建て，出力レベルを E_i に設定すると，(X_i,Y_i) からの距離が \sqrt{E_i}以下の家でテレビ放送が見られるようになる (2点 (a,b) と (c,d) の距離は \sqrt{(a-c)^2+(b-d)^2} で与えられる)．ただし，電波塔の出力レベルを E_i に設定すると E_i のエネルギーを消費する．すべての家でテレビ放送が見られるようにしつつ，できるだけ K 本の電波塔で消費されるエネルギーの合計 (以下，単に「消費エネルギー」と呼ぶ) を少なくしたい．電波塔は家がある座標に建てることもできるし，同じ座標に 2 つ建てることもできる．

JOI国の家の座標が与えられた時，すべての家でテレビ放送が見られるように電波塔を建てる場所と出力レベルの設定を決めたい．

課題

JOI国の家の位置および K が与えられるので，電波塔を建てる場所と出力レベルの設定を出力せよ．消費エネルギーが少ないほど，あなたは高得点を得る．

制限

`1 \leqq N \leqq 500`	JOI 国の家の数
`1 \leqq K \leqq 30`	今回建てる電波塔の数
`0 \leqq A_i,B_i \leqq 1\,000\,000`	家の座標

入力

入力ファイルは以下の形式で与えられる．

1 行目には整数 N, K が空白を区切りとして書かれており，JOI 国の家の数が N, 今回建てる電波塔の数が K であることを表す．
続く N 行のうち i 行目(1 \leqq i \leqq N)には整数 A_i, B_i が空白を区切りとして書かれており，i 番目の家の座標が (A_i,B_i) であることを表す．

同じ座標に 2 つ以上の家があることはないとしてよい．

出力

出力の i 行目 (1 \leqq i \leqq K) には 3 つの整数 X_i, Y_i, E_i (0 \leqq X_i \leqq 1\,000\,000, 0 \leqq Y_i \leqq 1\,000\,000, 0 \leqq E_i \leqq 1\,000\,000\,000\,000\,(=10^{12})) を空白を区切りとして出力せよ．

提出方法

各入力データに対する出力を提出せよ．その際，出力のセクションで指定された形式に一致するかがチェックされる．

採点基準

各入力データに対し，あなたの得点は以下のように計算される．

参加者が提出した出力の中での，消費エネルギーの最小値を E_0 とする．あなたの提出した出力が問題の条件を満たさない場合，あなたの得点は0である．条件を満たす場合，あなたの提出した出力における消費エネルギーを E として，

\frac{E}{E_0} > 1.5 のとき，0
\frac{E}{E_0} \leqq 1.5 のとき，(4 \times (1.5-\frac{E}{E_0} )^2) \times 20 の小数第 1 位を四捨五入した値

があなたの得点となる．

入出力例

入力例	出力例
`10 3 0 300000 500000 800000 700000 200000 100000 500000 400000 900000 200000 1000000 300000 500000 300000 200000 500000 100000 1000000 0`	`200000 700000 160000000000 300000 300000 90000000000 750000 0 62500000000`

この入出力は下の図に対応している．各々の円が座標 (X_i, Y_i) から距離 \sqrt{E_i} 以下の範囲を表す．この場合，消費エネルギーは 160\,000\,000\,000+90\,000\,000\,000+62\,500\,000\,000=312\,500\,000\,000 (3125億) である．