题目内容

用加权 $K$-Means 把 $n$ 个样本点分成 $K$ 个簇，共迭代 $T$ 轮。第 $i$ 个点的坐标是 $(x_i, y_i)$，权重是 $m_i$。$K$ 个初始中心 $c_1, c_2, \ldots, c_K$ 已经给出，第 $j$ 个中心的坐标记为 $(a_j, b_j)$。

每一轮先用本轮开始时的中心完成全部分配，再统一更新中心。

• 分配：点 $i$ 到中心 $j$ 的距离平方为 $(x_i - a_j)^2 + (y_i - b_j)^2$。点归入距离平方最小的中心。若有多个中心并列，取编号 $j$ 最小的。
• 更新：若簇 $j$ 中至少有一个点，新中心为

$a_j = (\sum m_i x_i) / (\sum m_i)$，$b_j = (\sum m_i y_i) / (\sum m_i)$

求和只包括本轮归入簇 $j$ 的点。若簇 $j$ 为空，该中心保持不变。

输出 $T$ 轮结束后的 $K$ 个中心。迭代中间不舍入。

输入描述

第一行三个整数 $n$、$K$、$T$。

接下来 $n$ 行，每行三个整数 $x_i$、$y_i$、$m_i$。

接下来 $K$ 行，每行两个整数 $a_j$、$b_j$。

约束

$1 \le n \le 200$

$1 \le K \le 10$

$1 \le T \le 20$

$|x_i|, |y_i|, |a_j|, |b_j| \le 1000$

$1 \le m_i \le 100$

输出描述

输出 $K$ 行，第 $j$ 行两个数，依次为 $a_j$、$b_j$，中间一个空格。每个数四舍五入保留 $4$ 位小数；第 $5$ 位小数为 $5$ 时，向远离 $0$ 的方向进位。

样例1

输入

3 2 1
0 0 1
4 0 3
10 0 1
0 0
10 0

输出

3.0000 0.0000
10.0000 0.0000

说明

到两个中心的距离平方：

• 点 $(0,0)$：$0$ 与 $100$，归入中心 $1$
• 点 $(4,0)$：$16$ 与 $36$，归入中心 $1$
• 点 $(10,0)$：$100$ 与 $0$，归入中心 $2$

中心 $1$ 的新坐标为 $((1 \cdot 0 + 3 \cdot 4) / 4,\ 0) = (3, 0)$。中心 $2$ 只有点 $(10,0)$，保持 $(10, 0)$。

样例2

输入

1 2 1
0 0 5
-2 0
2 0

输出

0.0000 0.0000
2.0000 0.0000

说明

点 $(0,0)$ 到两个中心的距离平方都是 $4$，归入编号更小的中心 $1$。中心 $1$ 更新为 $(0, 0)$。中心 $2$ 没有点，保持 $(2, 0)$。