Has K-Means Converged?
Wexford Couriers is now repeating the round over and over, and needs a rule for when to stop. The planners call the layout settled once no site is still shifting to speak of. They set a tolerance for that in map units, and the layout counts as settled only when every single site moved less than it -- strictly less, so a site that moved exactly the tolerance has not settled. Movement means the straight-line distance from where a site sat at the start of the round to where it sits now, judged one site at a time rather than pooled across the map.
Task: Print whether the layout has settled.
Input
The first line holds one integer k, the number of sites, and the tolerance, separated by a single space. Each of the next k lines holds four numbers separated by single spaces: one site's two coordinates before the round, followed by its two coordinates after it.
Output
One line: converged if every site moved less than the tolerance, or not converged if even one site did not.
Example:
Input:
2 0.1
0 0 0.05 0.02
10 10 10.03 9.98
Output:
converged
Sign in to solve this problem
Reading problems is free for everyone — solving them (Run, Submit, and tracking what you've solved) needs an account.
Sign in