聚类

dim = 2      #二维
n_data = 10000    #10000个数据点
iter_times = 10

def l2_dist(x1, x2):          #欧氏距离
    sum = 0
    for i in range(len(x1)):
        sum += (x1[i] - x2[i]) ** 2
    return sum ** (1/2)

#计算中心
def centroid(l):
    res = [0] * dim
    for i in range(dim):
        for a in l:
            res[i] += data[a][i]
    for i in range(dim):
        res[i] /= len(l)
    return res

def CalCentroids(l):
    res = []
    for i in l:
        res.append(centroid(i))
    return res

K = int(input())

data = []
for i in range(n_data):
    data += [list(map(float, input().strip().split()))]

#随机分配
clusters= []
for i in range(K):
    clusters.append([])
for i in range(n_data):
    pos = i % K
    clusters[pos].append(i)

#迭代
for _ in range(iter_times):
    sum_dist = 0
    centroids = CalCentroids(clusters)
    for i in range(K):
        clusters[i] = []
    for i in range(n_data):
        best_c = 0
        best_d = 9999999999
        for j in range(K):
            d = l2_dist(centroids[j], data[i])
            if d < best_d:
                best_c = j
                best_d = d
        sum_dist += best_d
        if len(clusters[best_c]) == 0:
            clusters[best_c] = []
        clusters[best_c].append(i)

print(sum_dist)

# for i in range(K):
#     print(f'{clusters[i][0]} {clusters[i][1]}')