手撕K-Means，华为快递配送题AC代码（逐行注解）

import sys

import math

# ========== 1. 距离函数 ==========

def dist(p1, p2):

"""计算两点之间的欧氏距离"""

return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

# ========== 2. K-Means 聚类算法 ==========

def kmeans(pts, k, max_iter=50, eps=1e-4):

"""

pts: 所有点的坐标列表

k: 聚类数量

max_iter: 最大迭代次数

eps: 收敛阈值

"""

n = len(pts) # 点的总数

# ----- 2.1 初始化聚类中心 -----

# 计算每个点到原点 (0,0) 的距离

d2ori = []

for i, p in enumerate(pts):

d = math.sqrt(p[0] ** 2 + p[1] ** 2)

d2ori.append((d, i, p)) # (距离, 索引, 点坐标)

# 排序：按距离从小到大，距离相同按输入顺序

d2ori.sort(key=lambda x: (x[0], x[1]))

# 取前 k 个点作为初始聚类中心

centers = [d2ori[i][2] for i in range(k)]

# ----- 2.2 迭代优化 -----

for _ in range(max_iter):

# 分配每个点到最近的聚类中心

belong = [-1] * n # belong[i] 表示点 i 属于哪个簇

for i, p in enumerate(pts):

best = 0

best_d = dist(p, centers[0])

for j, c in enumerate(centers):

d = dist(p, c)

if d < best_d:

best_d = d

best = j

belong[i] = best

# 重新计算每个簇的中心点（平均值）

new_c = []

for j in range(k):

# 找出属于第 j 簇的所有点

clu = [pts[i] for i in range(n) if belong[i] == j]

if clu:

# 计算 x 和 y 的平均值

avg_x = sum(p[0] for p in clu) / len(clu)

avg_y = sum(p[1] for p in clu) / len(clu)

new_c.append((avg_x, avg_y))

else:

# 如果某个簇没有点，保留原中心

new_c.append(centers[j])

# 计算所有中心点的移动距离之和

move = sum(dist(centers[j], new_c[j]) for j in range(k))

centers = new_c

# 如果移动距离小于阈值，收敛，停止迭代

if move < eps:

break

return centers

# ========== 3. 主函数 ==========

def solve():

# 读取所有输入数据

data = sys.stdin.read().strip().split()

if not data:

return

idx = 0

k = int(data[idx]); idx += 1 # 社区个数（聚类数）

n = int(data[idx]); idx += 1 # 快递包裹总数

sp = float(data[idx]); idx += 1 # 行驶速度 km/h

# 读取所有点的坐标

pts = []

for _ in range(n):

x = float(data[idx]); idx += 1

y = float(data[idx]); idx += 1

pts.append((x, y))

# 执行 K-Means 聚类，得到 k 个社区中心

centers = kmeans(pts, k)

# 计算每个中心到原点的距离，并按距离排序

d2ori = []

for c in centers:

d = math.sqrt(c[0] ** 2 + c[1] ** 2)

d2ori.append((d, c))

d2ori.sort(key=lambda x: x[0]) # 按距离升序排序

# 提取排序后的中心坐标

sorted_centers = [c for _, c in d2ori]

# ----- 计算总路程 -----

origin = (0.0, 0.0) # 起点

total = 0.0

cur = origin

# 起点 → 第1个中心 → 第2个中心 → ... → 第k个中心

for c in sorted_centers:

total += dist(cur, c)

cur = c

# 最后一个中心 → 起点

total += dist(cur, origin)

# 计算总时间（秒），向下取整

# 时间 = 距离 / 速度，速度单位 km/h，需要乘以 3600 转换为秒

print(int(total / sp * 3600))

if __name__ == "__main__":

solve()