记录编号	402252	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1781.[国家集训队2012]最远点	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.878 s
提交时间	2017-05-05 17:23:09	内存使用	23.18 MiB

#include<cstdio>
typedef long long ll;
const int N=1e6+10;
int T,n,x[N],y[N],ans[N];
ll sqr(ll x){return x*x;}
ll dis(int i,int j){return sqr(x[i]-x[j])+sqr(y[i]-y[j]);}
int st[N],top,L[N],R[N];
bool cmp(int i,int x,int y){//若对i来说x比y优,返回1
	ll a=dis(i,x),b=dis(i,y);
	if (x<i||x>i+n) a=-a;
	if (y<i||y>i+n) b=-b;
	if (x>n) x-=n;
	if (y>n) y-=n;
	return a==b?x<y:a>b;
}
//依据决策单调性的分治优化dp
void solve(int L,int R,int l,int r){
	int mid=(L+R)>>1,k=l;
	for (int i=l;i<=r;i++) if (cmp(mid,i,k)) k=i;
	ans[mid]=k;
	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);
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		for (int i=1;i<=n;i++){
			scanf("%d%d",&x[i],&y[i]);
			x[i+n]=x[i];
			y[i+n]=y[i];
		}
		solve(1,n,1,n*2);
		for (int i=1;i<=n;i++) printf("%d\n",ans[i]>n?ans[i]-n:ans[i]);
	}
	return 0;
}