AI001. 多维样本聚类器

"""Exact global-minimum epsilon selection for integer-input K-Means."""
import sys


def select(point, centers, counts):
    numerators = [sum((x*q-s)**2 for x,s in zip(point, row))
                  for row,q in zip(centers, counts)]
    denominators = [q*q for q in counts]
    best = 0
    for i in range(1, len(centers)):
        if numerators[i]*denominators[best] < numerators[best]*denominators[i]:
            best = i
    for i in range(len(centers)):
        gap = numerators[i]*denominators[best] - numerators[best]*denominators[i]
        if gap*10**9 <= denominators[i]*denominators[best]:
            return i


def format_coordinate(total, count):
    if abs(total)*2000 < count:
        return '0.00'
    value = (200*abs(total)+count)//(2*count)
    return ('-' if total < 0 and value else '') + f'{value//100}.{value%100:02d}'


def solve(text):
    data = iter(map(int, text.split()))
    n,d,k,t = (next(data) for _ in range(4))
    centers = [[next(data) for _ in range(d)] for _ in range(k)]
    points = [[next(data) for _ in range(d)] for _ in range(n)]
    counts = [1]*k
    for _ in range(t):
        sums = [[0]*d for _ in range(k)]
        sizes = [0]*k
        for point in points:
            index = select(point, centers, counts)
            sizes[index] += 1
            for j in range(d):
                sums[index][j] += point[j]
        for i in range(k):
            if sizes[i]:
                centers[i], counts[i] = sums[i], sizes[i]
    return '\n'.join(' '.join(format_coordinate(s,q) for s in row)
                     for row,q in zip(centers, counts))


if __name__ == '__main__':
    print(solve(sys.stdin.read()))