broadcasting1 - テレビ放送 Editorial /

Time Limit: 1 sec / Memory Limit: 64 MiB

AtCoder での提出方法

この提出先はテストケース 01 用です.このテストケースに対する出力ファイルを,言語 Text (cat) を選択して提出してください.

各テストケースの提出先: 01 | 02 | 03 | 04 | 05

入力データ

配点 : 20 点

問題文

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}\leqq1.5 のとき,\left(4\times\left(1.5 - \frac{E}{E_0}\right)^2\right)\times20 の小数第 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 億) である.

図


Source Name

JOI 2011-2012 春季トレーニング合宿 Contest Day2