import random
import time
from Tkinter import *

#######Globals. We define a canvas to draw the pts and the result#####
N = 150  
master = Tk()

###Canvas 4X for visual clarity
w = Canvas(master, width=4*N, height=4*N,background="white")
w.pack()

####### functions for drawing pts and lines on the 4X canvas###########
####### we leave out two rows and colums at the borders###########
def drawpoint(x,y,colour):
	x = x*4+2
	y = y*4+2
	w.create_rectangle(x-1,y-1,x+1,y+1, fill=colour) #zoomed pt as a 3x3 rectangle

def drawline(x1,y1,x2,y2,colour):
	x1 = x1*4+2
	y1 = y1*4+2
	x2 = x2*4+2
	y2 = y2*4+2
	w.create_line(x1,y1,x2,y2,width=3,fill=colour)

#########qsort may be useful#############
def partition(a,b,x,left,right):
	i = left
	j = right
	#INV:a[left..i-1] <= x; a[j+1..right] > x
	#       left <= i <= right+1;left-1 <= j <= right; i <= j+1
	while (i <= j):
		if (a[i] <= x):
			i = i+1
		else:
			a[i],a[j] = a[j],a[i]
			b[i],b[j] = b[j],b[i]
			j = j-1
	p = j
	#assert: all a[left..p] <= x; all a[p+1..right] > x
	return p

#a and b are two arrays. sorts (a,b) on a
def qsort(a,b,left,right):
	if (left < right):
		p = partition(a,b,a[left],left+1,right)
		a[left],a[p] = a[p],a[left]
		b[left],b[p] = b[p],b[left]
		qsort(a,b,left,p-1)
		qsort(a,b,p+1,right)


######### Your functions here ####################

#def closest(x,y,n):
#	...blah..blah
#	#assert:(x[k],y[k]) and (x[l],y[l]) are the closest pair
#	return (k,l)

########## Main stuff #################
x = []
y = []

i = 0
while (i < N):
	x.append(random.randint(0,N-1))
	y.append(random.randint(0,N-1))
	#assert: (x[i],y[i]) is a random point
	drawpoint(x[i],y[i],"blue")
	i = i+1

#comment out the folowing 2 lines and run this program to see the points
(k,l) = closest(x,y,N)
drawline(x[k],y[k],x[l],y[l],"red"); #draw a red line connecting the closest pair


mainloop()