记录编号	250450	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]最远点	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	10.536 s
提交时间	2016-04-15 09:27:07	内存使用	25.08 MiB

#define null NULL
#define maxn 500001ul

#define rg_ register

#define fastcall __attribute__((optimize("-Os")))
#define inline __inline__ __attribute__((always_inline))

#define ll long long

#include <stdio.h>
#include <algorithm>

struct Point{int x,y,id;}sp[maxn];

int n,cnt,qx,qy,aid,ans[maxn];
ll adis,tmp;

fastcall inline ll Min(rg_ ll a,rg_ ll b){return a<b?a:b;}
fastcall inline ll Max(rg_ ll a,rg_ ll b){return a>b?a:b;}
fastcall inline ll sqr(rg_ ll x){return x*x;}
inline bool cmpx(const Point &a,const Point &b) {return a.x<b.x;}
inline bool cmpy(const Point &a,const Point &b) {return a.y<b.y;}

struct node{
	node *left,*right;
	Point point;
	int minx,maxx,miny,maxy;
	inline void init(const Point &x){
		point=x;
		left=right=null;
		minx=maxx=x.x;
		miny=maxy=x.y;
		return;
	}
	inline void update(node *&x){
		if(x==null) return;
		if(x->minx<minx) minx=x->minx;
		if(x->miny<miny) miny=x->miny;
		if(x->maxx>maxx) maxx=x->maxx;
		if(x->maxy>maxy) maxy=x->maxy;
		return;
	}
	inline ll max_dis(){return Max(sqr(qx-minx),sqr(qx-maxx))+Max(sqr(qy-miny),sqr(qy-maxy));}
}*root,kd[maxn];

void build(node *&rt,int l,int r,int d){
	if(l>r) return;
	rg_ int mid=(l+r)>>1;
	std::nth_element(sp+l,sp+mid,sp+r+1,d?cmpx:cmpy);
	rt=&kd[++cnt],rt->init(sp[mid]);
	build(rt->left,l,mid-1,d^1);
	build(rt->right,mid+1,r,d^1);
	rt->update(rt->left);
	rt->update(rt->right);
	return;
}

void ask(node *rt){
	if(rt==null) return;
	tmp=sqr(qx-rt->point.x)+sqr(qy-rt->point.y);
	if(tmp>adis||(tmp==adis&&rt->point.id<aid)) adis=tmp,aid=rt->point.id;
	rg_ ll disL=rt->left!=null?rt->left->max_dis():-2,disR=rt->right!=null?rt->right->max_dis():-2;
	if(disL<=adis&&disR<=adis) return;
	if(disL>disR){
        ask(rt->left);
        if(disR>adis) ask(rt->right);
	}
	else{
        ask(rt->right);
        if(disL>adis) ask(rt->left);
	}
	return;
}

inline int in(){
	rg_ int x=0,c=getchar();bool flag=false;
	while(c<'0'||c>'9'){
        if(c=='-') flag=true;
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	if(flag) return -x;
	return x;
}

int main(){
	freopen("nt2012_dis.in","r",stdin);
	freopen("nt2012_dis.out","w",stdout);
	rg_ int T=in();
	while(T--){
		n=in(),root=null,cnt=0;
		for(rg_ int i=1;i<=n;i++) sp[i].x=in(),sp[i].y=in(),sp[i].id=i;
		build(root,1,n,0);
		for(rg_ int i=1;i<=n;i++){
			adis=-1,qx=sp[i].x,qy=sp[i].y,ask(root);
			ans[sp[i].id]=aid;
		}
		for(rg_ int i=1;i<=n;i++) printf("%d\n",ans[i]);
	}
 	return 0;
}