import time
import sys

def closestpair(a,b,beg,end,index):
    global count
    global rec
    rec=rec+1
    ind=[]
    ind.append(0)
    ind.append(0)
    ind.append(0)
    ind.append(0)
    mid=(beg+end)/2
    if mid==beg:
        count=count+1
        x=(a[end]-a[beg])*(a[end]-a[beg])
        y=(b[end]-b[beg])*(b[end]-b[beg])
        z=int((x+y)**0.5)
        index[0]=a[beg]
        index[1]=b[beg]
        index[2]=a[end]
        index[3]=b[end]
        
        return z
    z1=closestpair(a,b,beg,mid,index)
    z2=closestpair(a,b,mid+1,end,ind)
    
    if z1>z2:
        mn=z2
        count=count+1
        for k in range(len(index)):
            index[k]=ind[k]  
    else:
        mn=z1
    x=[]
    c=[]
    d=[]
    i=mid
    while i>=beg:
        if a[i]<mn:
            c.append(a[i])
            d.append(b[i])
            x.append(i)
        i=i-1
    
    e=[]
    f=[]
    i=mid+1
    z=[]
    while i<= end:
        if a[i]<mn:
            e.append(a[i])
            f.append(b[i])
            z.append(i)
        i=i+1
    i=0
    j=0
    num=0
    while i<len(c):
        while j<len(e):
            x=(e[j]-c[i])*(e[j]-c[i])
            y=(f[j]-d[i])*(f[j]-d[i])
            z=int((x+y)**0.5)
            if mn>z:
                mn=z
                count=count+1
                for k in range(len(index)):
                    index[k]=0
                index[0]=c[i]
                index[1]=d[i]
                index[2]=e[j]
                index[3]=f[j]
            j=j+1
        i=i+1
    return mn
count=0
rec=0
f1=open('in12_4.txt','r')
f2=open('out_24_12_4.txt','w')
a=[]
b=[]
n=int(f1.readline())
j=0
index=[]
index.append(0)
index.append(0)
index.append(0)
index.append(0)
h=time.clock()
for i in range(n):
    row=f1.readline()
    lst=row.split(',')
    a.append(int(lst[0]))
    b.append(int(lst[1]))

i=0
while i <n:
    x=a[i]
    y=b[i]
    y
    j=i-1
    while j>=0:
        if a[j]> x :
            a[j+1]=a[j]
            b[j+1]=b[j]
            j=j-1
        else:
            break        
    a[j+1]=x
    b[j+1]=y
    i=i+1

g=closestpair(a,b,0,n-1,index)
d=time.clock() 
f2.write('Closest Pair :')
f2.write(str(index[0])+','+str(index[1])+' & ')
f2.write(str(index[2])+','+str(index[3]))
f2.write('\nNo. of Comparisons='+str(count))
f2.write('\nNo of recursive calls='+str(rec))
f2.write('\nTime Taken='+str(d-h))
mem=sys.getsizeof(x)+sys.getsizeof(y)+sys.getsizeof(a)+sys.getsizeof(b)+sys.getsizeof(j)+sys.getsizeof(i)
f2.write('\nMemory Used='+str(mem)) 
f1.close()
f2.close()