%pylab inline
import random
import math
import numpy as np
import matplotlib.pyplot as plt

def s(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

def genPoints(num, a0, b0, a1, b1):
    points = []
    for i in range(num):
        points.append([random.randint(a0, b0), random.randint(a1, b1)])
    return points
    
#clusters
level1 = []
level2 = []
level3 = []

#count of points
n = 1000
e = 0.1

#points
points = genPoints(n, 0, 350000, 0, 1800)

# centres
clevel1 = [0, 0]
clevel2 = [1, 1]
clevel3 = [2, 2]

while 1:
    templ1 = []
    templ2 = []
    templ3 = []
    
    for p in points:
        sl1 = s(p, clevel1)
        sl2 = s(p, clevel2)
        sl3 = s(p, clevel3)
        if sl1 <= sl2 and sl1 <= sl3:
            templ1.append(p)
        elif sl2 <= sl1 and sl2 <= sl3:
            templ2.append(p)
        else:
            templ3.append(p)
    
    newclevel1 = [0, 0]
    newclevel2 = [0, 0]
    newclevel3 = [0, 0]
    
    for i in templ1:
        newclevel1[0] += i[0]
        newclevel1[1] += i[1]
    if len(templ1) != 0:
        newclevel1[0] /= len(templ1)
        newclevel1[1] /= len(templ1)
        
    for i in templ2:
        newclevel2[0] += i[0]
        newclevel2[1] += i[1]
    if len(templ2) != 0:
        newclevel2[0] /= len(templ2)
        newclevel2[1] /= len(templ2)
        
    for i in templ3:
        newclevel3[0] += i[0]
        newclevel3[1] += i[1]
    if len(templ3) != 0:
        newclevel3[0] /= len(templ3)
        newclevel3[1] /= len(templ3)
        
    if s(newclevel1, clevel1) <= e and s(newclevel2, clevel2) <= e and s(newclevel3, clevel3) <= e:
        level1 = templ1
        level2 = templ2
        level3 = templ3
        break
    
    clevel1 = newclevel1
    clevel2 = newclevel2
    clevel3 = newclevel3
    
#print "L1", level1
#print "L2", level2
#print "L3", level3

l1X = []
l1Y = []
for i in level1:
    l1X.append(i[0])
    l1Y.append(i[1])
    
l2X = []
l2Y = []
for i in level2:
    l2X.append(i[0])
    l2Y.append(i[1])
    
l3X = []
l3Y = []
for i in level3:
    l3X.append(i[0])
    l3Y.append(i[1])
    
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(l1X, l1Y, c='b', marker='^')
ax.scatter(l2X, l2Y, c='r', marker='D')
ax.scatter(l3X, l3Y, c='y', marker='o')
ax.axis([0, 355000, 0, 1900])
plt.show()