using namespace std;
#include <algorithm>
#include <cstdio>
#include <string>
#include <ctime>
#define DIM 8192
#define N 300001
#include <cmath>
#define maxh 666013
char ax[DIM+16];
int pz;


inline void cit(int &x)
{
            x=0;
            while((ax[pz]<'0' || ax[pz]>'9') && (ax[pz]!='-'))
                        if(++pz==DIM)fread(ax, 1, DIM, stdin), pz=0;
           
            int neg=0;
            if(ax[pz]=='-')
            {
                        neg=1;
                        if(++pz==DIM)fread(ax, 1, DIM, stdin),pz=0;
            }
         
            while(ax[pz]>='0' && ax[pz]<='9')
            {
                        x=x*10+ax[pz]-'0';
                         if(++pz==DIM)fread(ax,1, DIM, stdin),pz=0;
            }
            if(neg) x=-x;
}


struct point { int x, y;point(){}; point(int a, int b){x=a;y=b;};};

point a[N];
int n,m;

inline long long distanta(point a, point b)
{
	return (long long)(a.x-b.x)*(a.x-b.x)+(long long)(a.y-b.y)*(a.y-b.y);
}

struct nod { int x, y,nr_nodes,height;bool dir,deleted; nod *l, *r;};

struct cmp1{
	bool operator()(const point &a, const point &b)const
	{
		if(a.x < b.x) return 1;
		return 0;
	}
};

struct cmp2{
	bool operator()(const point &a, const point &b)const
	{
		if(a.y < b.y) return 1;
		return 0;
	}
};

typedef nod* kd;

kd R,nil;

inline void init()
{
	nil=new nod;
	nil->l=nil->r=0;
	nil->x=nil->y=0;
	nil->dir=0;
	nil->nr_nodes=0;
	nil->height=0;
	R=nil;
}

//point b[N];

int T;
void ino(kd &n,int t)
{
	if(n == 0) return;
//	printf("(%d %d %d) ", n->x, n->y,n->dir);
	ino(n->l,t+1);
	ino(n->r,t+1);
	//if(n->deleted == 0) printf("(%d %d) ", n->x, n->y);
	if(T<t)T=t;
}

int Nr=0;

inline int get_height(kd n)
{
	if(n == 0) return 0;
	
	return max(get_height(n->l),get_height(n->r)) +1;
}


kd build(int l, int r,int dir)
{
	if(l >= r) 
	{
		kd t=new nod;
		t->x=a[l].x;
		t->y=a[l].y;
		t->dir=dir;
		t->l=t->r=nil;
		t->nr_nodes=1;
		t->deleted=0;
		t->height=1;
		return t;
	}
	
	int m=(l+r)>>1;
	if(dir)
	{	
		nth_element(a+l, a+m,a+r+1, cmp1());
	
	}
	
	else
	{		
		nth_element(a+l,a+m, a+r+1, cmp2());
    	}
	
	

	kd t=new nod;
	t->x=a[m].x;
	t->y=a[m].y;
	t->dir=dir;
	t->l=build(l, m-1, dir^1);
	t->r=build(m+1, r, dir^1);
	t->nr_nodes=t->l->nr_nodes + t->r->nr_nodes + 1;
	t->deleted=0;
	t->height=max(t->l->height, t->r->height)+1;
	return t;
}

inline void df(kd &n)
{
	if(n == nil) return;
	
	df(n->l);
	df(n->r);
	
	if(n->deleted == 0) a[++Nr]=point(n->x, n->y);
	delete n;
}


inline void rebalance(kd &n)
{
	fprintf(stderr,"balansam %d ",n->height);
	Nr=0;
	df(n);
	n=build(1,Nr,1);
	fprintf(stderr,"balansat %d\n", n->height);
}
	

int nrb;

inline void insert(kd &n, point P,bool dir)
{
	if(n == nil)
	{
		n=new nod;
		n->l=n->r=nil;
		n->x=P.x;
		n->y=P.y;
		n->dir=rand()&1;
		n->nr_nodes=1;
		n->height=1;
		return;
	}
	
	if(P.x == n->x && P.y == n->y)
	{
		if(n->deleted)
		{
			n->deleted=0;
			++n->nr_nodes;
		}
		return;
	}
	
	if(n->height > 30) {++nrb;rebalance(n);	}
	if(n->dir == 1)
	{
		if(P.x < n->x) insert(n->l, P,dir^1);//rand()&1);
		else  insert(n->r, P,dir^1);//rand()&1);
	
	}
	else
	{
		if(P.y < n->y) insert(n->l,P,dir^1);//rand()&1);
		else insert(n->r, P,dir^1);//rand()&1);
	}
	


	
	n->nr_nodes=n->l->nr_nodes + n->r->nr_nodes + 1;
	n->height=max(n->l->height,n->r->height)+1;
}

inline void sterge(kd n, point P)
{
	if(n == nil) return ;
	
	if(P.x == n->x && P.y == n->y) 
	{
		n->deleted=1;
		--n->nr_nodes;
		return;
	}
	
	if(n->dir == 1)
	{
		if(P.x < n->x) sterge(n->l, P);
		else sterge(n->r, P);
	}
	else
	{
		if(P.y < n->y) sterge(n->l, P);
		else sterge(n->r, P);
	}
	
	n->nr_nodes=n->l->nr_nodes + n->r->nr_nodes + 1;
}

void read()
{
	freopen("forum.in","r",stdin);
	cit(n);cit(m);
	int i;
	for(i=1;i<=n;++i) cit(a[i].x), cit(a[i].y);
	
}



//nearest neighbor O(sqrt(n))


long long dist=0x3f3f3f3f;
inline void query(kd n, point P)
{
	if(n == nil) return;
	
	if(n->dir == 1)
	{
		if(P.x <= n->x) query(n->l, P);
		else query(n->r, P);
	}
	else
	{
		if(P.y <= n->y) query(n->l, P);
		else query(n->r, P);
	}
	 
	if(n->deleted == 0)
	if(distanta(P, point(n->x, n->y)) < dist)
		dist=distanta(P, point(n->x, n->y));
	
	
}

inline int intersect(int X0, int Y0, int X1, int Y1, point P, long long R)
{
	if(P.x>=X0 && P.x <= X1 && P.y >= Y0 && P.y <=Y1) return 1;
	if(P.y>=Y0 && P.y<=Y1 && distanta(point(X0, P.y), P) <=R) return 1;
	if(P.y>=Y0 && P.y<=Y1 && distanta(point(X1, P.y), P) <=R) return 1;
	if(P.x>=X0 && P.x<=X1 && distanta(point(P.x, Y0), P) <=R) return 1;
	if(P.x>=X0 && P.x<=X1 && distanta(point(P.x, Y1), P) <=R) return 1;
	
	
	//return 0;
	
	if(distanta(point(X0, Y0), P) <= R) return 1;
	if(distanta(point(X1, Y0), P) <=R ) return 1;
	if(distanta(point(X0, Y1), P) <=R ) return 1;
	if(distanta(point(X1, Y1), P) <=R ) return 1;

	return 0;
}

int nr;

inline void quer(kd n,point P, int X0, int Y0, int X1, int Y1)
{
	//++nr;
	if(n == nil) return ;
	if(intersect(X0, Y0, X1, Y1, P, dist) == 0) return;
	
	long long d=distanta(P, point(n->x, n->y));
	if(n->deleted == 0) 
	if(dist > d) dist=d;
	
	if( n->dir == 1)
	{
		quer(n->l, P, X0, Y0,n->x, Y1);
		quer(n->r, P,n->x,Y0, X1, Y1);
	}
	else
	{
		quer(n->l, P, X0, Y0, X1, n->y);
		quer(n->r ,P,X0, n->y, X1, Y1);
		
	}
}


	
//end nearest neighbor

// begin rectangle query 

inline void rect(kd n,point P, int X0, int Y0, int X1, int Y1)
{
	//++nr;
	if(n == nil) return ;
	//if(intersect(X0, Y0, X1, Y1, P, dist) == 0) return;
	
	long long d=distanta(P, point(n->x, n->y));
	if(dist > d) dist=d;
	
	if( n->dir == 1)
	{
		quer(n->l, P, X0, Y0,n->x, Y1);
		quer(n->r, P,n->x,Y0, X1, Y1);
	}
	else
	{
		quer(n->l, P, X0, Y0, X1, n->y);
		quer(n->r ,P,X0, n->y, X1, Y1);
		
	}
}



//end rectangle query
struct cmp{
	bool operator()(const point &a, const point &b)const
	{
		if(a.x < b.x) return 1;
		return 0;
		
	}
};
int main()
{
//	freopen("forum.out","w",stdout);
//	read();
	n=10000;
	srand(time(0));
	int i;
	
	a[1].x=32000;
	a[1].y=32000;
	for(i=2;i<=n;++i) 
	{
		if(i&1) a[i].x=a[i-1].x-1, a[i].y=a[i-1].y;
		else a[i].x=a[i-1].x, a[i].y=a[i-1].y-1;
	}
	
	//for(i=1;i<=n;++i) a[i].x=rand()%32000, a[i].y=rand()%32000;

//	sort(a+1, a+n+1,cmp());
	double s=clock();
	init();
	for(i=1;i<=n;++i) 
	{
		//printf("%d %d\n", a[i].x, a[i].y);
		insert(R, a[i],1);
	
	//	if(R->height > 30) rebalance(R);
	}
	
	
	
		//rebalance(R);
	//R=build(1,n,1);
	T=0;
	ino(R,0);
	printf("hight: %d\n", R->height);
	printf("rebalansari: %d\n", nrb);
	//R=nil;
	//R=build(1,n,1);
	//ino(R,0);x
	for(i=1;i<=n;++i) 
	{
//		sterge(R, a[i]);
	}
		//insert(R, a[i], 1);
	
	for(i=1;i<=n;++i)
	{
		point q=point(rand()%32000, rand()%32000);
		query(R, q);
		quer(R, q,-32000,-32000, 32000, 32000);
	}
	
	long long D;
	int t;
	point P;
	//m=100000;
	//int Sol=0;
	
	/*
	for(i=1;i<=m;++i)
	{
		//P.x=rand()%212;
		//P.y=rand()%210;
		cit(P.x); cit(P.y);
		
		dist=0x3f3f3f3f;
		query(R, P);

		quer(R,P,-32000, -32000, 32000, 32000);
		
		D=distanta(P, point(0,0));
	
		if(dist<=D) { printf("NU\n");}
		else  {printf("DA\n");}
		
		
	}
	*/
	//for(i=1;i<=100000;++i) query(R, point(rand(), rand()));
	fprintf(stderr,"%lf\n", (clock()-s)/(double)CLOCKS_PER_SEC);
	//ino(R,0);
	//printf("%d\n", T);
	return 0;
}