记录编号	167945	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]最远点	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	10.693 s
提交时间	2015-06-29 20:50:40	内存使用	34.62 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define UseFREAD
#ifdef UseFREAD
#define getc() *(file_ptr++)
#define FreadLenth 10000000
char CHARPOOL[FreadLenth], *file_ptr = CHARPOOL;
#else
#define getc() getchar() 
#endif
#ifdef DEBUG
#include <ctime>
#endif
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 500020;
typedef long long LL;

int N, Ans[maxn], px[2];
struct Point{int x[2], id;}P[maxn];
inline LL dist(const Point &a){
	LL ta = a.x[0]-px[0], tb = a.x[1]-px[1];
	return ta * ta + tb * tb;
}
bool cmp0(const Point &a, const Point &b){return a.x[0] < b.x[0];}
bool cmp1(const Point &a, const Point &b){return a.x[1] < b.x[1];}
typedef bool (*CMP) (const Point&a, const Point&b);
CMP _cmp[2] = {cmp0, cmp1};

struct Node{
	Point *cut;
	bool spl;
	int size, mx[2], mn[2];
	Node *son[2];
	void build(Point*, Point*);
	Point *Query();
}node[maxn], *iter;

void Node::build(Point *l, Point *r){
	son[0] = son[1] = NULL;
	if((size = r - l) == 1){
		cut = l;
		mx[0] = mn[0] = cut->x[0];
		mx[1] = mn[1] = cut->x[1];
		return;
	}
	mx[0] = mn[0] = l->x[0];
	mx[1] = mn[1] = l->x[1];
	for(Point *it = l+1;it < r;++it){
		mx[0] = max(mx[0], it->x[0]), mx[1] = max(mx[1], it->x[1]);
		mn[0] = min(mn[0], it->x[0]), mn[1] = min(mn[1], it->x[1]);
	}
	spl = (mx[0] - mn[0]) < (mx[1] - mn[1]);
	cut = l + (size >> 1); nth_element(l, cut, r, _cmp[spl]);
	if(cut != l)(son[0] = iter++)->build(l, cut);
	if(cut != r-1)(son[1] = iter++)->build(cut+1, r);
}

LL Dis;Point *ans;
inline bool cover(Node *n){
	LL a = n->mx[0] - px[0], b = n->mx[1] - px[1],
	   c = n->mn[0] - px[0], d = n->mn[1] - px[1];
	a *= a, b *= b, c *= c, d *= d;
	return (a > c ? a : c) + (b > d ? b : d) <= Dis;
}

Point *Node::Query(){
	LL t;
	bool dir = px[spl] > cut->x[spl];
	if((t = dist(*cut)) > Dis)Dis = t, ans = cut;
	if(son[dir^1] && !cover(son[dir^1]))son[dir^1]->Query();
	if(son[dir] && !cover(son[dir]))son[dir]->Query();
}

inline void init(){
	iter = node;
	getd(N);
	for(int i = 0;i < N;++i)P[i].id = i+1, getd(P[i].x[0]), getd(P[i].x[1]);
	(iter++)->build(P, P+N);
}

inline void work(){
	int i;
	for(i = 0;i < N;++i){
		Dis = 0, ans = P+i, px[0] = P[i].x[0], px[1] = P[i].x[1];
		node->Query();
		Ans[P[i].id] = ans->id;
	}
	for(i = 1;i <= N;++i)printf("%d\n", Ans[i]);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(nt2012_dis);
#endif

#ifdef UseFREAD
	fread(file_ptr, 1, FreadLenth, stdin);
#endif
	int T;getd(T);
	while(T--){
		init();
		work();
	}

#ifdef DEBUG
	printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}