1 #include<bits/stdc++.h>  2 #define cl(a,b) memset(a,b,sizeof(a))  3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl  4 using namespace std;  5 typedef long long ll;  6 typedef pair<int,int> pii;  7   8 #define inf (1e9+20)  9 #define ll long long 10 #define ls ch[x][0] 11 #define rs ch[x][1] 12  13 const int maxn = 2e5+10; 14  15 struct P 16 { 17     int a[2] , num; 18     ll dis; 19 } p[maxn]; 20  21 int now , k = 2; 22  23 bool cmp(int a,int b) 24 { 25     return p[a].a[now] < p[b].a[now]; 26 } 27  28 ll dist(P a,P b) 29 { 30     ll sum = 0; 31     for(int i=0; i<k; i++) 32     { 33         sum += 1ll*(a.a[i]-b.a[i])*(a.a[i]-b.a[i]); 34     } 35     return sum; 36 } 37  38 int ch[maxn][2] , co[maxn] , root; 39  40 void pushup(int x) 41 { 42     co[x] = co[ls] + co[rs] + 1; 43 } 44  45 const double alp = 0.75; 46  47 bool isbad(int x) 48 { 49     return max(co[ls],co[rs]) > alp*co[x] + 5; 50 } 51  52 void build(int &x,int l,int r,int a[],int no) 53 { 54     if( l > r ) 55     { 56         x = 0; 57         return ; 58     } 59     int mid = l+r>>1; 60     now = no; 61     nth_element(a+l,a+mid,a+r+1,cmp); 62     x = a[mid]; 63     build(ls,l,mid-1,a,no^1); 64     build(rs,mid+1,r,a,no^1); 65     pushup(x); 66 } 67  68 P ans; 69  70 void Find(int x,int y,int no) 71 { 72     if(!x) return ; 73     ll dis = dist(p[y],p[x]); 74     if( x != y ) 75     { 76         if( dis < ans.dis || (dis==ans.dis&&p[x].num < ans.num) ) 77         { 78             ans = p[x]; 79             ans.dis = dis; 80         } 81     } 82     ll d = p[y].a[no] - p[x].a[no]; 83     Find(ch[x][d>0],y,no^1); 84     if( d*d <= ans.dis ) 85     {//找平方 86         Find(ch[x][d<=0],y,no^1); 87     } 88 } 89  90 int Fa , No; 91  92 int Insert(int &x,int fa,int k,int no) 93 { 94     if( x == 0 ) 95     { 96         x = k; 97         return 0; 98     } 99     int t = p[x].a[no]<p[k].a[no];100     int r = Insert(ch[x][t],x,k,no^1);101     pushup(x);102     if( isbad(x) ) r = x , Fa = fa , No = no;103     return r;104 }105 106 int su[maxn] , len;107 108 void travel(int x)109 {110     if(x==0) return ;111     travel(ls);112     su[len++] = x;113     travel(rs);114 }115 116 void Insert(int k)117 {118     int x = Insert(root,0,k,0);119     if(x)120     {121         int tmp = x;122         len = 0;123         travel(x);124         build(x,0,len-1,su,No);125         if(Fa) ch[Fa][ch[Fa][1]==tmp] = x;126         else root = x;127     }128 }129 130 int si;131 132 void newnode(int x,int y,int id)133 {134     si++;135     p[si].a[0] = x;136     p[si].a[1] = y;137     p[si].num = id;138     ch[si][0] = ch[si][1] = 0;139     co[si] = 1;140 }141 142 void init()143 {144     si = 0;145     ch[0][0] = ch[0][1] = 0;146     co[0] = 0;147     root = 0;148 }149 150 int num[maxn];151 152 int main()153 {154 //    freopen("in.txt","r",stdin);155     int T,n;156     scanf("%d",&T);157     while(T--)158     {159         scanf("%d",&n);160         init();161         int x,y;162         for(int i=1; i<=n; i++)163         {164             scanf("%d%d",&x,&y);165             newnode(x,y,i);166             Insert(si);167         }168         for(int i=1; i<=n; i++)169         {170             ans.dis = 4e18;171             Find(root,i,0);172             printf("%lld\n",ans.dis);173         }174     }175     return 0;176 }/*177 178 2179 10180 17 41181 0 34182 24 19183 8 28184 14 12185 45 5186 27 31187 41 11188 42 45189 36 27190 15191 0 0192 1 2193 2 3194 3 2195 4 0196 8 4197 7 4198 6 3199 6 1200 8 0201 11 0202 12 2203 13 1204 14 2205 15 0206 207 */