K-Means One Iteration

Run one full k-means iteration: assign every point to its nearest centroid (squared Euclidean distance, lowest index on ties) and then move each centroid to the mean of its assigned points. A centroid that receives no points stays where it was.

Implement solve(X, C).

Returns. Return a tuple (labels, new_centroids): an integer array of length n_points and a (K, d) float array.

Examples

Example 1

Input:

solve([[0.0, 0.0], [1.0, 0.0], [10.0, 0.0]], [[0.0, 0.0], [10.0, 0.0]])

Output:

([0, 0, 1], [[0.5, 0.0], [10.0, 0.0]])

Example 2

Input:

solve([[0.0, 0.0], [1.0, 0.0]], [[0.0, 0.0], [100.0, 100.0]])

Output:

([0, 0], [[0.5, 0.0], [100.0, 100.0]])