Run k-means on points in the plane and measure how tight the clusters it finds are.
What to build
A program that runs two-dimensional k-means from given starting centroids and reports the result.
Requirements
- Each round: assign every point to its nearest centroid (squared Euclidean distance; ties to the earlier centroid), then move each centroid to the mean of its points; an empty cluster keeps its centroid.
- Stop after the first round that leaves every centroid unchanged (at most 100 rounds).
- Print
centroid i: (X, Y)for each centroid,inertia Iandrounds R, with X, Y and I to 2 decimal places.
Input
Line 1: n and k. Then n lines x y. Then k lines with the starting centroids.
Output
k + 2 lines.
Constraints
1 ≤ n ≤ 500, 1 ≤ k ≤ 10.
Example
Input:
6 2
1 1
1 2
2 1
8 8
8 9
9 8
1 1
2 1
Output:
centroid 1: (1.33, 1.33)
centroid 2: (8.33, 8.33)
inertia 2.67
rounds 3
Why it works
The final assignment and the final centroids agree with each other, so no single step can lower the inertia further: that is where k-means stops.
Examples
6 2 1 1 1 2 2 1 8 8 8 9 9 8 1 1 2 1
centroid 1: (1.33, 1.33) centroid 2: (8.33, 8.33) inertia 2.67 rounds 3
2 1 0 0 2 2 5 5
centroid 1: (1.00, 1.00) inertia 4.00 rounds 2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Use squared Euclidean distances; on a tie, the earlier centroid wins.
Hint 2
A round is one assignment and one update; stop after the first round in which no centroid changed.
Hint 3
The inertia is the sum, over points, of the squared distance to the centroid of their final cluster.
Solution
Show one correct solution (try it yourself first)
n, k = map(int, input().split())
points = [tuple(map(float, input().split())) for _ in range(n)]
centroids = [tuple(map(float, input().split())) for _ in range(k)]
def d2(a, b):
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
rounds = 0
for rounds in range(1, 101):
labels = [min(range(k), key=lambda j: (d2(p, centroids[j]), j)) for p in points]
new = []
for j in range(k):
mine = [p for p, label in zip(points, labels) if label == j]
new.append((sum(p[0] for p in mine) / len(mine), sum(p[1] for p in mine) / len(mine)) if mine else centroids[j])
changed = new != centroids
centroids = new
if not changed:
break
labels = [min(range(k), key=lambda j: (d2(p, centroids[j]), j)) for p in points]
for i, (x, y) in enumerate(centroids):
print(f"centroid {i + 1}: ({x:.2f}, {y:.2f})")
print(f"inertia {sum(d2(p, centroids[label]) for p, label in zip(points, labels)):.2f}")
print(f"rounds {rounds}")