记录编号	252791	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]最远点	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	2.545 s
提交时间	2016-04-21 07:27:35	内存使用	13.66 MiB

#include<bits/stdc++.h>
#define ll long long
#define inf 0x7fffffff
using namespace std;
inline int read(){
	int s=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0';
	return s*f;
}
inline void print(int x){
	if(!x)return;
	print(x/10);
	putchar(x%10+'0');
}
int ans[500010];
struct node{int x,y,id;}a[1000010];
int n;
ll sqr(ll x){return x*x;}
bool cmp(int i,int j,int k){
	ll x=sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y);
	ll y=sqr(a[i].x-a[k].x)+sqr(a[i].y-a[k].y);
	if(j<i||j>i+n)x=-x;
	if(k<i||k>i+n)y=-y;
	return x==y?a[j].id>a[k].id:x<y;
}
void solve(int L,int R,int l,int r){
	int mid=(L+R)>>1;int k=l;
	for(int i=l+1;i<=r;++i)if(cmp(mid,k,i))k=i;
	ans[mid]=a[k].id;
	if(L<mid)solve(L,mid-1,l,k);
	if(R>mid)solve(mid+1,R,k,r);
}
int main(){
	freopen("nt2012_dis.in","r",stdin);
	freopen("nt2012_dis.out","w",stdout);
	int T;T=read();
	for(;T;--T){
		n=read();
		for(int i=1;i<=n;++i)a[i].x=read(),a[i].y=read(),a[i].id=i,a[i+n]=a[i];
		solve(1,n,1,n+n);
		for(int i=1;i<=n;++i)
			print(ans[i]),puts("");
	}return 0;
}