用户分群

[编程题]用户分群

热度指数：88 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

某电商平台希望根据用户的购物行为对用户进行分群，以便制定差异化的运营策略。

每位用户有三个特征指标： purchase_amount（月均消费金额） visit_frequency（月均访问次数） return_rate（退货率，已归一化）你需要实现 KMeans 聚类算法，将用户划分为若干个群体。

KMeans 算法的流程如下：给定 K 个初始聚类中心，计算每个数据点到各聚类中心的欧氏距离，将数据点分配到距离最近的聚类中心所在的组。然后对每个组重新计算中心点（即该组内所有数据点各维度的算术平均值），完成一轮迭代。重复上述过程指定的迭代次数后，输出最终的 K 个聚类中心，每个维度的值保留两位小数（四舍五入）。

欧氏距离的计算公式为： $d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$

输入描述:

第一行一个正整数 K，表示聚类中心的个数。
接下来 K 行，每行三个浮点数，表示初始聚类中心的三个特征值。
下一行一个正整数，表示迭代次数。
下一行一个正整数 m，表示数据点的个数。
接下来 m 行，每行三个浮点数，表示一个数据点的三个特征值。

输出描述:

输出 K 行，每行三个数值，表示迭代结束后各聚类中心的三个特征值，保留两位小数，四舍五入。

示例1

输入

输出

8.33 18.33 29.33
41.67 51.67 61.67

说明

初始中心为 [10,20,30] 和 [40,50,60]，共 6 个数据点，迭代 2 次。
第 1 轮：前三个点 (8,18,25)、(12,22,35)、(5,15,28) 距离中心 [10,20,30] 更近，分到第一组；后三个点 (42,48,58)、(38,52,62)、(45,55,65) 距离中心 [40,50,60] 更近，分到第二组。更新中心为 [8.33,18.33,29.33] 和 [41.67,51.67,61.67]。
第 2 轮：分配结果不变，中心保持不变。

示例2

输入

输出

5.00 5.00 5.00
14.00 16.00 14.00
26.00 24.00 26.00

说明

初始中心为 [5,5,5]、[15,15,15]、[25,25,25]，共 4 个点，迭代 1 次。
(4,4,4) 和 (6,6,6) 距离中心 [5,5,5] 最近，分到第一组，新中心为 [(4+6)/2,(4+6)/2,(4+6)/2]=[5,5,5]。
(14,16,14) 距离中心 [15,15,15] 最近，分到第二组，新中心为 [14,16,14]。
(26,24,26) 距离中心 [25,25,25] 最近，分到第三组，新中心为 [26,24,26]。