from time import clock
import sys
def fun(xcord,ycord,b,e,final):
    global ncomp
    m=(b+e)/2
    lst=[0,0,0,0]
    if m==b:
        #Compute the distance between two points.
        x=(xcord[e]-xcord[b])*(xcord[e]-xcord[b])
        y=(ycord[e]-ycord[b])*(ycord[e]-ycord[b])
        dist=int(x+y)           #Distance formula: d=(x^2+y^2)**0.5. As we just need to compare distances, we'll not take square root.
        final[0]=xcord[b]
        final[1]=ycord[b]
        final[2]=xcord[e]
        final[3]=ycord[e]
        return dist
    dist1=fun(xcord,ycord,b,m,final)
    dist2=fun(xcord,ycord,m+1,e,lst)
    if dist1<=dist2:
        ncomp+=1
        min=dist1
    else:
        min=dist2
        for i in xrange(len(final)):
            final[i]=lst[i]
            #Six lists taken to store index, x-coord. and y-coord. of the point.
    a1=[]
    a2=[]
    a3=[]
    a4=[]
    a5=[]
    a6=[]
    i=m+1
    while i<= e:                    #It will found the minimum distance point on the left side.
        if xcord[i]<min:
            ncomp+=1
            a4.append(i)
            a5.append(xcord[i])
            a6.append(ycord[i])
        i+=1
    i=m
    while i>=b:                     #Binary search algorithm. It will found the minimum distance point on the right side.
        if xcord[i]<min:
            ncomp+=1
            a1.append(i)
            a2.append(xcord[i])
            a3.append(ycord[i])          
        i-=1
    i,j=0,0
    while i<len(a2):
        while j<len(a5):
            x=(a5[j]-a2[i])*(a5[j]-a2[i])
            y=(a6[j]-a3[i])*(a6[j]-a3[i])
            dist=int(x+y)
            if min>dist:
                ncomp+=1
                min=dist
                final[0]=a2[i]
                final[1]=a3[i]
                final[2]=a5[j]
                final[3]=a6[j]
            j+=1
        i+=1
def main():
    start=clock()
    global ncomp
    ncomp=0
    try:
        f=open("12_4.txt","r")
        f1=open("out_34_sec12_4.txt","w")
        npoints=int(f.readline())
        xcord=[]                                #To store x-coordinate of points.
        ycord=[]                                #To store y-coordinate of points.
        for i in xrange(npoints):
            point=f.readline()
            coord=point.split(",")
            xcord.append(int(coord[0]))
            ycord.append(int(coord[1]))
        f.close()
        u=0
        for v in xrange(npoints):
            x=xcord[v]
            y=ycord[v]
            for u in xrange(v-1,-1-1):
                if xcord[u]>x:
                    ncomp+=1
                    xcord[u+1]=xcord[u]
                    ycord[u+1]=ycord[u]
                else:
                    break        
            xcord[u+1]=x
            ycord[u+1]=y
        final=[0,0,0,0]                         #To store the final points.
        fun(xcord,ycord,0,npoints-1,final)
        for d in xrange(1,len(final),2):
            f1.write("%d,%d\n" %(final[d-1],final[d]))
        end=clock()
        f1.write("Time taken by the program is : %f seconds" %(end-start))
        f1.write("\nTotal comparisons in the program are: %d" %(ncomp))
        mem=sys.getsizeof(f)+sys.getsizeof(f1)+sys.getsizeof(npoints)+sys.getsizeof(xcord)+sys.getsizeof(ycord)+sys.getsizeof(u)+sys.getsizeof(v)+sys.getsizeof(x)+sys.getsizeof(final)+sys.getsizeof(d)
        f1.write("\nMemory used by the program is : %d bytes." %mem)
    except IOError:
        print "Input file not found in the directory."


main()