AT_joisc2012_broadcasting2 テレビ放送
题目描述
在JOI国，计划开始电视广播服务。JOI国有$N$户家庭。为了让所有这些家庭都能观看电视广播，需要建造一些广播塔。
这次，JOI国的国王决定建造K座广播塔。如果将第$i$个广播塔建在坐标$(X_i,Y_i)$处，并将其功率设定为$E_i$，则距离$(X_i,Y_i)$的距离不超过$E_i$的家庭可以接收到电视信号(两个点$(a,b)$和$(c,d)$之间的距离用$\sqrt{((a-c)^2+(b-d)^2)}$表示。)但是，设置广播塔的功率为$E_i$将消耗$E_i$的能量。希望在确保所有家庭都能接收到电视信号的同时，尽量减少这$K$座广播塔的总能量消耗（以下简称“能量消耗”）。广播塔可以建在已有的家庭坐标上，也可以在同一坐标上建造多个广播塔。
给定JOI国中各家庭的坐标和$K$的值，要求确定广播塔的位置和功率设置，使得所有家庭都能接收到电视信号，并且能量消耗尽可能少。
输入格式
* 第1行有两个整数$N$和$K$
* 接下来的$N$行中，第$i$行$(1\le i\le N)$有两个整数$A_i$和$B_i$，用空格分隔，表示第$i$个家庭的坐标为$(A_i,B_i)$。
输出格式
输出的第$i$行$(1\le i\le K)$包含三个整数$X_i,Y_i,E_i$，用空格分隔，表示广播塔的位置和功率设置。
### 输入输出样例
#### 输入 #1
```
10 3
0 300000
500000 800000
700000 200000
100000 500000
400000 900000
200000 1000000
300000 500000
300000 200000
500000 100000
1000000 0
```
#### 输出 #1
```
200000 700000 160000000000
300000 300000 90000000000
750000 0 62500000000
```
说明/提示
* $1\le N\le 500$
* $1\le K\le 30$
* $0\le A_i,B_i\le 1,000,000$
#### 评分标准
对于每个输入数据，分数将按照以下方式计算：
* 设你提交的输出中的最小能量消耗为E0。
* 如果你的输出不满足问题条件，得分为0。
* 如果满足条件，设你的输出中的能量消耗为E，计算公式如下：
* 如果E/E0 > 1.5，得分为0。
* 如果E/E0 $\le$1.5，则得分为$4\times (\frac{1.5-\frac{E}{E0}}{1.5})^2\times 20$ 取小数点后1位进行四舍五入。