One Step of k-means

Story

A delivery company has k pickup lockers placed around town and n customers who each use their nearest locker. Every night the company moves each locker to the centre of its customers. That is one iteration of k-means, the clustering algorithm behind customer segmentation, image palettes and vector quantisation. Implement it from scratch.

Task

You are given n points and k current centroids in d dimensions. Perform one iteration:

1. Assign every point to the nearest centroid by Euclidean distance. If two or more centroids are equally near, pick the one with the lowest index. Indexes start at 0.
2. Update every centroid to the mean of the points assigned to it. A centroid that received no points stays where it was.
3. Inertia = the sum, over all points, of the squared distance to the centroid the point was assigned to (the old centroids used in step 1).

Input

• Line 1: n k d (1 ≤ n ≤ 2000, 1 ≤ k ≤ 8, 1 ≤ d ≤ 4)
• Next n lines: the coordinates of a point (d numbers)
• Next k lines: the coordinates of a centroid (d numbers)

Output

• Line 1: n integers, the centroid index of every point in input order, separated by spaces
• Next k lines: the new centroids (d numbers each)
• Last line: the inertia

Print at least 4 decimals; every number within 0.0001 of the exact value is accepted.

Example

6 2 2
1 1
1.5 2
3 4
5 7
3.5 5
4.5 5
1 1
5 7

Output:

0 0 0 1 1 1
1.8333 2.3333
4.3333 5.6667
24.75

The point (3, 4) is exactly 13 away (squared) from both centroids, so the lower index 0 wins. The inertia is 0 + 1.25 + 13 + 0 + 6.25 + 4.25 = 24.75.

6 2 2
1 1
1.5 2
3 4
5 7
3.5 5
4.5 5
1 1
5 7