题解 | 小红的 AI 配送聚类优化

import math

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

def solve():
    # 1.输入处理
    try:
        msg = input().split()
        if not msg: return 
        K, N, V_kmh = int(msg[0]), int(msg[1]), float(msg[2])

        points = []
        for _ in range(N):
            points.append(list(map(float, input().split())))
    except EOFError:
        return 
    
    # 2.初始化聚类中心
    if K >= N:
        centers = [p[:] for p in points]
    else:
        points_with_dist = []
        for i in range(N):
            d = get_dist((0,0), points[i])
            points_with_dist.append((points[i], d, i))
        points_with_dist.sort(key = lambda x: x[1])
        centers = [points_with_dist[i][0][:] for i in range(K)]
    
    # 3. K-Means迭代
    for _ in range(50):
        clusters = [[] for _ in range(len(centers))]

        # 分配阶段
        for p in points:
            min_d = float('inf')
            best_idx = 0
            for i,c in enumerate(centers):
                d = get_dist(p, c)
                if d < min_d:
                    min_d = d
                    best_idx = i
            clusters[best_idx].append(p)
        
        # 更新阶段
        total_move = 0
        new_centers = []
        for i in range(len(centers)):
            if not clusters[i]:
                new_centers.append(centers[i])
                continue
            
            # 计算平均值
            avg_x = sum(p[0] for p in clusters[i]) / len(clusters[i])
            avg_y = sum(p[1] for p in clusters[i]) / len(clusters[i])
            new_p = [avg_x, avg_y]

            total_move += get_dist(centers[i], new_p)
            new_centers.append(new_p)
        
        centers = new_centers

        # 终止条件
        if total_move < 1e-4:
            break
    
    # 4.路径规划
    centers.sort(key = lambda x: get_dist((0,0), x))

    total_path = 0
    curr_pos = [0.0, 0.0]
    for c in centers:
        total_path += get_dist(curr_pos, c)
        curr_pos = c
    total_path += get_dist(curr_pos, [0.0,0.0])

    # 5.耗时计算
    total_seconds = (total_path / V_kmh) * 3600
    print(int(total_seconds))


solve()