K-Means算法

题意

给定 个二维坐标点（基站位置），要求用 K-Means 聚类算法将它们分成 组。然后用轮廓系数评估每个簇的质量，找出平均轮廓系数最低的那个簇，输出该簇质心坐标（保留两位小数，银行家舍入）。

关键规则：

• 初始中心取前 个点
• 轮廓系数 ，其中 是点 到本簇其他点的平均欧式距离， 是到最近其他簇所有点的平均距离
• 若簇只有 1 个点（或更少），

思路

这题没有复杂的算法设计，就是一道"照着说明书实现"的模拟题。但细节不少，咱们把它拆成三步。

第一步：K-Means 聚类

K-Means 本身很标准：

1. 拿前 个点当初始中心
2. 每个点归到最近的中心（用欧式距离的平方比较就行，省个 sqrt）
3. 重新计算每个簇的质心（坐标均值）
4. 重复直到分配不再变化

有个小问题要注意：如果某个簇在某轮变空了怎么办？ 保留上一轮的中心不变就好。实际上在本题数据范围下不太会出现，但防御性编程没坏处。

第二步：计算轮廓系数

轮廓系数是衡量聚类好坏的经典指标，直觉上：

• 越小，说明点 跟自己人越近——好
• 越大，说明点 离外人越远——也好
• 所以 越接近 1 越好，越接近 -1 越差

对每个点算 和 ，然后求 。每个簇内所有 取平均，就是这个簇的得分。

实现上可以先预处理所有点对的欧式距离矩阵，后面反复查表就行。，距离矩阵也就 ，完全没有压力。

第三步：输出

找得分最低的簇，算质心坐标，用银行家舍入（Python 的 Decimal 模块天然支持 ROUND_HALF_EVEN）保留两位小数输出。

复杂度

• K-Means 迭代：每轮 ，通常几十轮收敛
• 距离矩阵：
• 轮廓系数：（每个点要跟所有其他点算距离）
• 总体 ， 毫无压力

代码

import sys
import math
from decimal import Decimal, ROUND_HALF_EVEN

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    k = int(input_data[idx]); idx += 1

    points = []
    for i in range(n):
        x = int(input_data[idx]); idx += 1
        y = int(input_data[idx]); idx += 1
        points.append((float(x), float(y)))

    # 初始中心：前 k 个点
    centers = [points[i] for i in range(k)]

    # K-Means 迭代
    for _ in range(1000):
        labels = []
        for px, py in points:
            best_c = 0
            best_d = float('inf')
            for c in range(k):
                cx, cy = centers[c]
                d = (px - cx) ** 2 + (py - cy) ** 2
                if d < best_d:
                    best_d = d
                    best_c = c
            labels.append(best_c)

        new_centers = []
        for c in range(k):
            members = [points[i] for i in range(n) if labels[i] == c]
            if len(members) == 0:
                new_centers.append(centers[c])
            else:
                mx = sum(p[0] for p in members) / len(members)
                my = sum(p[1] for p in members) / len(members)
                new_centers.append((mx, my))

        if new_centers == centers:
            break
        centers = new_centers

    # 建簇
    clusters = [[] for _ in range(k)]
    for i in range(n):
        clusters[labels[i]].append(i)

    # 预处理距离矩阵
    dist = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            d = math.sqrt((points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2)
            dist[i][j] = d
            dist[j][i] = d

    # 计算每个簇的平均轮廓系数
    cluster_scores = []
    for c in range(k):
        members = clusters[c]
        if len(members) <= 1:
            cluster_scores.append(0.0)
            continue

        s_sum = 0.0
        for p in members:
            a_p = sum(dist[p][q] for q in members if q != p) / (len(members) - 1)

            b_p = float('inf')
            for c2 in range(k):
                if c2 == c or len(clusters[c2]) == 0:
                    continue
                avg_d = sum(dist[p][q] for q in clusters[c2]) / len(clusters[c2])
                if avg_d < b_p:
                    b_p = avg_d

            if b_p == float('inf'):
                s_p = 0.0
            else:
                denom = max(a_p, b_p)
                s_p = (b_p - a_p) / denom if denom > 0 else 0.0

            s_sum += s_p

        cluster_scores.append(s_sum / len(members))

    # 找得分最低的簇
    worst_c = 0
    worst_score = cluster_scores[0]
    for c in range(1, k):
        if cluster_scores[c] < worst_score:
            worst_score = cluster_scores[c]
            worst_c = c

    # 输出质心，银行家舍入
    members = clusters[worst_c]
    cx = sum(points[i][0] for i in members) / len(members)
    cy = sum(points[i][1] for i in members) / len(members)

    dx = Decimal(str(cx)).quantize(Decimal('0.01'), rounding=ROUND_HALF_EVEN)
    dy = Decimal(str(cy)).quantize(Decimal('0.01'), rounding=ROUND_HALF_EVEN)

    print(f"{dx},{dy}")

solve()