记录编号	162715	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]最远点	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	10.245 s
提交时间	2015-05-19 09:01:13	内存使用	38.64 MiB

/****************************************\
* Author : ztx
* Title  : [cogs] 1781. [国家集训队2012]最远点
* ALG    : bl
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
//typedef long long ll ;
typedef double ll ;
int CH , NEG ;
#define  Strlen  10000000LL
char Stream[Strlen] , *ptr=Stream ;
inline int GETCHAR() { return *ptr++ ; }
template <typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=GETCHAR() , CH<'!') ;
    if (CH == '-') NEG = true , CH = GETCHAR() ;
    while (ret = ret*10+CH-'0' , CH=GETCHAR() , CH>'!') ;
    if (NEG) ret = -ret ;
}

void in(int &x){
	x=0;
	while(*ptr<48) ptr++;
	while(*ptr>47) x=x*10+*ptr++-48;
}

#include <algorithm>

#define  maxn  500010LL
#define  maxt  1048577LL
#define  max(x,y) ((x)>(y)?(x):(y))
#define  min(x,y) ((x)<(y)?(x):(y))
#define  sqr(x)   (((ll)x)*(x))
#define  l(o)     (o<<1)
#define  r(o)     (o<<1|1)

struct P { int x , y ; int id ; } points[maxn] ;
inline bool cmpx(const P&a,const P&b) { return a.x < b.x; }
inline bool cmpy(const P&a,const P&b) { return a.y < b.y; }

int ans[maxn] ;

struct KD {
	P *p ;
	KD *c[2] ;
	int maxx,maxy,minx,miny;
	inline void init(P*p) ;
	inline void update(KD*son) ;
	inline ll maxdis() ;
} kd[maxt] , *null = &kd[0] , *root=null ;
inline void KD::init(P*p) {
	this->p = p ;
	maxx = minx = p->x ;
	maxy = miny = p->y ;
	c[0] = c[1] = null ;
}
inline void KD::update(KD*son) {
	if (son == null) return ;
	if (son->maxx > maxx) maxx = son->maxx ;
	if (son->maxy > maxy) maxy = son->maxy ;
	if (son->minx < minx) minx = son->minx ;
	if (son->miny < miny) miny = son->miny ;
}
int qx , qy , qa ;
ll qw , dis , tx , ty ;
inline ll KD::maxdis() {
	if (this == null) return 0 ;
	tx = max(sqr(qx-minx),sqr(qx-maxx)) ;
	ty = max(sqr(qy-miny),sqr(qy-maxy)) ;
	dis = tx + ty ;
	return dis ;
}
inline void Build(KD*&now,int o,int L,int R,int d=0) {
	if (L > R) { now = null ; return ; }
	now = &kd[o] ;
	int M = L+R>>1 ;
	std::nth_element(points+L,points+M,points+R+1,d?cmpx:cmpy) ;
	now->init(&points[M]) ;
	Build(now->c[0],l(o),L,M-1,d^1) ;
	Build(now->c[1],r(o),M+1,R,d^1) ;
	now->update(now->c[0]) ;
	now->update(now->c[1]) ;
}
inline void Query(KD*now,int d=0) {
	if (now == null) return ;
	dis = sqr(qx-now->p->x)+sqr(qy-now->p->y) ;
	if (dis>qw || (dis==qw&&now->p->id<qa)) qw = dis , qa = now->p->id ;
	ll ttx = now->c[0]->maxdis() ;
	ll tty = now->c[1]->maxdis() ;
	if (ttx<qw && tty<qw) return ;
	bool First = d?(qx<now->p->x):(qy<now->p->y) ;
	if (First) {
		if (tty>=qw)
		Query(now->c[1],d^1) ;
		if (ttx>=qw)
		Query(now->c[0],d^1) ;
	} else {
		if (ttx>=qw)
		Query(now->c[0],d^1) ;
		if (tty>=qw)
		Query(now->c[1],d^1) ;
	}
}
inline void Query(int p) {
	qx = points[p].x , qy = points[p].y , qa = 0 , qw = -1 ;
	Query(root) ;
	ans[points[p].id] = qa ;
}

int main() {
int Time , i , n ;
	#define READ
	#ifdef  READ
		freopen("nt2012_dis.in" ,"r",stdin ) ;
		freopen("nt2012_dis.out","w",stdout) ;
	#endif
	fread(Stream,1,10000000,stdin);
	for (read(Time) ; Time --> 0 ; ) {
		read(n) ;
		Rep (i , 1 , n) {
			read(points[i].x) , read(points[i].y) ;
			points[i].id = i ;
		}
		Build(root , 1 , 1 , n) ;
		Rep (i , 1 , n)
			Query(i) ;
		Rep (i , 1 , n)
			printf("%d\n", ans[i]) ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}