All problems

Has K-Means Converged?

mediumPythonK-Means Clustering

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

Discussion

Sign in to join the discussion — reading is open to everyone.

Loading comments…