记录编号	252839	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]最远点	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	3.571 s
提交时间	2016-04-21 09:38:38	内存使用	25.09 MiB

#include<cstdio>

#define maxn 500010

using namespace std;

typedef long long ll;
struct point{
	ll x,y,id;
	void init(){
		scanf("%lld%lld",&x,&y);
	}
}p[maxn<<1];

int n,ans[maxn];

ll sqr(ll x)
{
	return x*x;
}

inline ll Dis(point a,point b)
{
	return sqr(a.x-b.x)+sqr(a.y-b.y);
}


bool cmp(int x,int i,int j)
{
	ll t1=Dis(p[x],p[i]),t2=Dis(p[x],p[j]);
	if(i<x||i>x+n) t1=-t1;
	if(j<x||j>x+n) t2=-t2;
	return t1>t2;
}

void devide(int l,int r,int ll,int rr)
{
	if(l>r) return ;
	int mid=l+r>>1;
	ans[mid]=ll;
	for(int i=ll+1;i<=rr;i++){
		if(cmp(mid,i,ans[mid])) ans[mid]=i;
	}
	devide(l,mid-1,ll,ans[mid]);
	devide(mid+1,r,ans[mid],rr);
}

int main()
{
	freopen("nt2012_dis.in","r",stdin);
	freopen("nt2012_dis.out","w",stdout);
	int T=0;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			p[i].init();
			p[i].id=i;
			p[i+n]=p[i];
		}
		devide(1,n,1,n+n);
		for(int i=1;i<=n;i++) printf("%d\n",ans[i]>n?ans[i]-n:ans[i]);
	}
	return 0;
}