class Arbol:
    # clave es la variable donde se guarda el dato
    clave=None
    # es una variable de tipo arbol que contiene el arbol de izq
    izq=None
    # es una variable de tipo arbol que contiene el arbol de izq
    der=None

class ArbolBidimensional(Arbol):
    def __init__(self,x,y,niv=0):
        self.clave=[x,y]
        self.niv=niv
    def __tab__(self,n):
        a=""
        for i in range(n):
            a=a+"\t"
        return a
    def __repr__(self):
        a=""
        a=a+str(self.clave)+"\n"
        if self.izq!=None:
            a=a+self.__tab__(self.izq.niv)+"Izq:"
            a=a+str(self.izq)+"\n"
        if self.der!=None:
            a=a+self.__tab__(self.der.niv)+"Der:"
            a=a+str(self.der)
        return a
    # Es la funcion que inserta un dato en el arbol
    def insertar(self, x,y,hor=True):
        # si la clave es menor que el dato a insertar
        if hor==True:
            if self.clave[0]<x:
                # si el hijo de derecha es nulo
                if self.der==None:
                    # entonces cree el hijo de izq con el dato
                    self.der=ArbolBidimensional(x,y,self.niv+1)
                    # si el hijo de derecha es nulo
                else:
                    self.der.insertar(x,y,False)
            elif self.clave[0]>x:
                if self.izq==None:
                    self.izq=ArbolBidimensional(x,y,self.niv+1)
                else:
                    self.izq.insertar(x,y,False)
            else:
                if self.clave[0]==x and self.clave[1]==y:
                    print "El dato "+str(x)+" "+str(y)+"ya existe"
                else:
                    self.insertar(x,y,False)
        elif hor==False:
            if self.clave[1]<y:
                # si el hijo de derecha es nulo
                if self.der==None:
                    # entonces cree el hijo de izq con el dato
                    self.der=ArbolBidimensional(x,y,self.niv+1)
                    # si el hijo de derecha es nulo
                else:
                    self.der.insertar(x,y,True)
            elif self.clave[1]>y:
                if self.izq==None:
                    self.izq=ArbolBidimensional(x,y,self.niv+1)
                else:
                    self.izq.insertar(x,y,True)
            else:
                if self.clave[0]==x and self.clave[1]==y:
                    print "El dato "+str(x)+" "+str(y)+"ya existe"
                else:
                    self.insertar(x,y,True)
    def buscar(self,x,y,hor=True):
        if self.clave==[x.y]:
            return True
        else:
            if hor==True:
                if self.clave[0]<x:
                    if self.der!=None:
                        return self.der.buscar(x,y,False)
                elif self.clave[0]>x:
                    if self.izq!=None:
                        return self.izq.buscar(x,y,False)
                else:
                    if self.clave[0]==x :
                        return self.insertar(x,y,False)
            elif hor==False:
                if self.clave[1]<y:
                    if self.der!=None:
                        return self.der.buscar(x,y,True)
                elif self.clave[1]>y:
                    if self.izq!=None:
                        return self.izq.buscar(x,y,True)
                else:
                    if self.clave[0]==x :
                        return self.insertar(x,y,True)

def recdatox():
   datox=int(raw_input("Digite x: "))
   return datox

def recdatoy():
   datoy=int(raw_input("Digite y: "))
   return datoy

def menu():
   opc=""
   arbol=None   
   while(opc!="0"):
	print "1). Insertar"
	print "2). Buscar"
	opc=raw_input("Escoja una opcion\n")
	if opc=="1":
		tmp=recdatox()
		tmp2=recdatoy()
		if arbol==None:
			arbol=ArbolBidimensional(tmp,tmp2)
		else:
			ArbolBidimensional.insertar(tmp,tmp2)
	elif opc=="2":
		tmp=recdatox()
		tmp2=recdatoy()
		if arbol==None:
			print "el arbol esta vacio"
		else:
			ArbolBidimensional.buscar(tmp,tmp2)		
	else:
		pass
	
menu()