import math
import random
 
centroid = lambda dots: tuple(map(lambda seq: sum(seq) / len(seq), zip(*dots)))
distance = lambda a, b: math.sqrt(sum((ai - bi) * (ai - bi) for ai, bi in zip(a, b)))
 
def kmeans(dots, k=None):
    n = len(dots)
    if k is None:
        k = int(math.sqrt(n / 2))
    means = random.sample(dots, k)
    while True:
        clusters = [[] for i in range(k)]
        for dot in dots:
            distances = [distance(dot, mean) for mean in means]
            i = distances.index(min(distances))
            clusters[i].append(dot)
        newmeans = [centroid(cluster) for cluster in clusters]
        if newmeans == means:
            break
        else:
            means = newmeans
    return clusters
 
if __name__ == "__main__":
    d = random.randint(1, 5)
    n = random.randint(10, 100)
    dots = [tuple(random.randint(0, 99) for i in range(d)) for j in range(n)]
    clusters = kmeans(dots)
    for cluster in clusters:
        print cluster
 

aW1wb3J0IG1hdGgKaW1wb3J0IHJhbmRvbQoKY2VudHJvaWQgPSBsYW1iZGEgZG90czogdHVwbGUobWFwKGxhbWJkYSBzZXE6IHN1bShzZXEpIC8gbGVuKHNlcSksIHppcCgqZG90cykpKQpkaXN0YW5jZSA9IGxhbWJkYSBhLCBiOiBtYXRoLnNxcnQoc3VtKChhaSAtIGJpKSAqIChhaSAtIGJpKSBmb3IgYWksIGJpIGluIHppcChhLCBiKSkpCgpkZWYga21lYW5zKGRvdHMsIGs9Tm9uZSk6CiAgICBuID0gbGVuKGRvdHMpCiAgICBpZiBrIGlzIE5vbmU6CiAgICAgICAgayA9IGludChtYXRoLnNxcnQobiAvIDIpKQogICAgbWVhbnMgPSByYW5kb20uc2FtcGxlKGRvdHMsIGspCiAgICB3aGlsZSBUcnVlOgogICAgICAgIGNsdXN0ZXJzID0gW1tdIGZvciBpIGluIHJhbmdlKGspXQogICAgICAgIGZvciBkb3QgaW4gZG90czoKICAgICAgICAgICAgZGlzdGFuY2VzID0gW2Rpc3RhbmNlKGRvdCwgbWVhbikgZm9yIG1lYW4gaW4gbWVhbnNdCiAgICAgICAgICAgIGkgPSBkaXN0YW5jZXMuaW5kZXgobWluKGRpc3RhbmNlcykpCiAgICAgICAgICAgIGNsdXN0ZXJzW2ldLmFwcGVuZChkb3QpCiAgICAgICAgbmV3bWVhbnMgPSBbY2VudHJvaWQoY2x1c3RlcikgZm9yIGNsdXN0ZXIgaW4gY2x1c3RlcnNdCiAgICAgICAgaWYgbmV3bWVhbnMgPT0gbWVhbnM6CiAgICAgICAgICAgIGJyZWFrCiAgICAgICAgZWxzZToKICAgICAgICAgICAgbWVhbnMgPSBuZXdtZWFucwogICAgcmV0dXJuIGNsdXN0ZXJzCgppZiBfX25hbWVfXyA9PSAiX19tYWluX18iOgogICAgZCA9IHJhbmRvbS5yYW5kaW50KDEsIDUpCiAgICBuID0gcmFuZG9tLnJhbmRpbnQoMTAsIDEwMCkKICAgIGRvdHMgPSBbdHVwbGUocmFuZG9tLnJhbmRpbnQoMCwgOTkpIGZvciBpIGluIHJhbmdlKGQpKSBmb3IgaiBpbiByYW5nZShuKV0KICAgIGNsdXN0ZXJzID0ga21lYW5zKGRvdHMpCiAgICBmb3IgY2x1c3RlciBpbiBjbHVzdGVyczoKICAgICAgICBwcmludCBjbHVzdGVyCg==