← 返回 microsoft 的题目列表Implement K-Means Clustering
类型：online_judge
Coding: Implement K-Means Clustering
Given n 2D points points[i] = (x_i, y_i) and a number of clusters k, implement k-means and output the cluster label for each point.
Task
Implement standard k-means:
Initialization: use the provided k initial centroids.
Repeat until convergence or max_iter:
Assignment: assign each point to the nearest centroid (Euclidean distance; break ties by smaller centroid index).
Update: recompute each centroid as the mean of points assigned to that cluster.
Stopping: stop if all centroid coordinate changes are < 1e-6 after an iteration, or if max_iter is reached.
Input (stdin)
Line 1: n k max_iter
Next n lines: x y
Next k lines: initial centroids cx cy
Output (stdout)
Print n lines; the i-th line is an integer cluster id (0..k-1) for point i.
Constraints
1 <= n <= 2000
1 <= k <= 50
Coordinates are floats with abs <= 1e4.
Test cases
(see tests below)
Example
Input
6 2 10
0 0
0 1
1 0
10 10
10 11
11 10
0 0
10 10
Output
0
0
0
1
1
1