Lloyd's algorithm by the rules
Run Lloyd's algorithm on points in the plane from the given initial centres. To make the answer unique, the rules are strict:
- The assign step: each point goes to the centre with the smallest squared Euclidean distance; on a tie, to the centre with the lower number.
- If the split did not change compared with the previous step, the algorithm stops (at the very first step there is no “previous” split, and it always counts as a change).
- The update step: each centre moves to the arithmetic mean of its points. A centre that got no points stays where it is.
- A pair of steps “assign + update” is one iteration; there are at most t iterations.
Input
The first line holds n, k, t (1 ≤ n ≤ 1000, 1 ≤ k ≤ 10, 1 ≤ t ≤ 100). Then n lines with the integer coordinates of the points, then k lines with the integer coordinates of the initial centres. Coordinates are at most 10⁴ in absolute value.
Output
The first line: the number of iterations performed (how many times the centres were updated). Then k lines: the final centres. The last line: the final inertia, the sum over all points of the squared distance to the nearest final centre. Fractions are checked with an error of 10⁻⁶.
Examples
Example 1
12 3 100 1 1 2 2 2 1 3 2 8 8 9 10 9 7 8 9 1 8 2 9 2 10 3 8 1 1 2 2 2 1
2 1.000000 1.000000 5.250000 8.625000 2.333333 1.666667 96.708333
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The article already has the code—check what it does with an empty group and with equal distances. What does the statement require?
2The idea
This is exactly the algorithm from the article, with no optimisation at all: n·k ≤ 10,000 comparisons per iteration, a hundred iterations—a million operations. The whole difficulty is in the rules: they make the result unique, and therefore checkable. Real libraries have to choose them too, and different libraries choose differently.
3Walkthrough
Keep the labels of the previous iteration (at first there are none). On every iteration compute the new labels, going through the centres in order and updating the best only on a strictly smaller distance—so a tie goes to the lower number. If the new labels equal the old ones, stop without increasing the counter. Otherwise remember the labels, increase the counter and update the centres from sums; leave a centre without points alone.
After the loop, compute the inertia afresh from the final centres: each point to the nearest of them. Note the test with the limit t = 1: after one iteration the algorithm has not converged yet, and the labels the centres were computed from no longer match the centres themselves. So the inertia is computed from distances, not from the old labels.
3+Solution
4Complexity
O(t·n·k) time, O(n + k) memory.
5Common mistakes
- An empty centre reset to zero. People dodge the division by zero by resetting the centre to (0, 0) or deleting it—but the statement says to leave the centre where it is. The third test puts one centre a thousand units from every point.
- The iteration counter. An iteration where the labels did not change does not count: the centres were not updated.
- Inertia from the old labels. Wrong when the algorithm is stopped by the limit t.