题目内容

实现 K-Means 聚类算法。

给定 $n$ 个样本的 $3$ 维特征，将其划分为 $k$ 个簇，输出各簇中心坐标。

算法步骤：

1. 初始化：使用前 $k$ 个样本作为初始聚类中心。
2. 分配：将每个样本分配到距离最近的聚类中心（欧氏距离）。
3. 更新：重新计算各簇中心为簇内样本均值。
4. 终止：最大迭代 $100$ 次，或所有簇中心移动距离之和 $\le 10^{-6}$。

输入描述

第一行包含两个整数 $n, k$（$1 \le k \le n \le 500$），表示用户数量和聚类簇数。

接下来 $n$ 行，每行 $3$ 个浮点数 $x_1, x_2, x_3$（$0 \le x_i \le 100$），分别表示用户的消费金额（归一化）、购买频次（归一化）、最近购买天数（归一化）。

输出描述

输出 $k$ 行，每行 $3$ 个浮点数，表示各簇中心的坐标，保留 $2$ 位小数。

按簇编号顺序输出（簇 $0$，簇 $1$，…，簇 $k-1$）。

样例 $1$

输入

6 2
10.0 20.0 5.0
12.0 22.0 6.0
11.0 21.0 4.0
80.0 5.0 50.0
82.0 6.0 48.0
78.0 4.0 52.0

输出

11.00 21.00 5.00
80.00 5.00 50.00

说明

• 簇 $0$ 包含前 $3$ 个用户（高频消费、低消费金额），中心为 $(11.00, 21.00, 5.00)$。
• 簇 $1$ 包含后 $3$ 个用户（低频消费、高消费金额），中心为 $(80.00, 5.00, 50.00)$。

样例 $2$

输入

4 2
0.0 0.0 0.0
1.0 1.0 1.0
100.0 100.0 100.0
99.0 99.0 99.0

输出

0.50 0.50 0.50
99.50 99.50 99.50

说明

第一次迭代后即收敛。簇 $0$ 中心为 $(0.5, 0.5, 0.5)$，簇 $1$ 中心为 $(99.5, 99.5, 99.5)$。