【场景】为了优化城市基站布局，需要把给定的基站坐标用 K-Means 聚成 k 组，并用轮廓系数评估每个簇的好坏。我们把“平均轮廓系数最低”的簇视为覆盖质量最差的簇，计划在该簇“质心位置”新增一座基站。请你输出这座新基站的坐标（四舍五入到两位小数，采用银行家舍入）。 【任务】 使用前 k 个点作为初始中心执行 K-Means。 轮廓系数定义：对样本 p，a(p) 是其与本簇其他样本的平均距离；b(p) 是其与“其他各簇”样本平均距离中的最小值；s(p)=(b(p)-a(p))max(a(p), b(p))。若样本所在簇大小≤1，则该样本 s(p)=0。 簇的得分为簇内样本 s(p) 的平均值。得分越低表示越差。 输出平均轮廓系数最低簇的“质心”（各坐标均值）。
输入描述:
第一行：n k（n 为点数，k 为簇数）接下来 n 行：每行两个整数 x y，表示一个基站的平面坐标取值范围：1 ≤ n ≤ 500，1 ≤ k ≤ 120，0 ≤ x ≤ 5000，0 ≤ y ≤ 3000
输出描述:
一行：新增基站坐标，格式为 x,y（保留两位小数）
示例1
输入
6 2
0 0
0 1
5 0
10 10
10 11
11 10
说明
初始中心为(0,0)、(0,1)。K-Means 收敛后，簇A≈{(0,0),(0,1),(5,0)}，质心≈(1.666...,0.333...)；簇B≈{(10,10),(10,11),(11,10)}，质心≈(10.333...,10.333...)。
簇A分散、与簇B距离也不算远，平均轮廓系数更低，因此选择簇A，其质心四舍五入（银行家舍入）为1.67,0.33。
备注:
本题由牛友@Charles 整理上传
加载中...