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;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;
R=nil;
}
//point b[N];
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;
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);
return t;
}
inline void insert(kd &n, point P)
{
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;
return;
}
if(P.x == n->x && P.y == n->y)
{
if(n->deleted)
{
n->deleted=0;
++n->nr_nodes;
}
return;
}
if(n->dir == 1)
{
if(P.x < n->x) insert(n->l, P);
else insert(n->r, P);
}
else
{
if(P.y < n->y) insert(n->l,P);
else insert(n->r, P);
}
n->nr_nodes=n->l->nr_nodes + n->r->nr_nodes + 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);
}
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;
}
//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=100000;
srand(time(0));
int i;
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) insert(R, a[i]);
//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;
}