gistfile1.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <map>
#include <functional>
#include <utility>
#include <vector>
#include <list>
#include <queue>
#include <complex>

using namespace std;

typedef list<int> EdgeList;
typedef vector<EdgeList> AdjList;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define FOR_EDGE(adj,v,it) for (EdgeList::iterator it = adj[v].begin(); \
    it != adj[v].end(); ++it)

struct Point : public complex<double> {
  int idx;
  double& operator[](int idx) {
    if (idx == 0) return complex<double>::real();
    else return complex<double>::imag();
  }
  const double& operator[](int idx) const {
    if (idx == 0) return complex<double>::real();
    else return complex<double>::imag();
  }
};
#define X(p) real(p)
#define Y(p) imag(p)


struct Cmp {
  int idx;
  Cmp(int idx): idx(idx){};
  bool operator()(const Point& p1, const Point& p2) const {
    return p1[idx] < p2[idx];
  }
};

Cmp cmps[] = {Cmp(0), Cmp(1)};

struct KDTree {
  Point *val;
  int cut_dim;
  KDTree *children[2];
  KDTree(){}
  KDTree(Point* pts, int start, int end, int cut_dim) {
    init(pts, start, end, cut_dim);
  }
  void init(Point *pts, int start, int end, int cut_dim);
  Point *find_nn(const Point& p, double& max_d) {
    double vd;
    Point *pt = NULL;
    Point *pt3 = NULL;
    bool lt = p[cut_dim] < (*val)[cut_dim];
    if (*val != p && (vd = abs((*val) - p)) < max_d) {
      pt = val;
      max_d = vd;
    }
    if (children[!lt]) {
      pt3 = children[!lt]->find_nn(p, max_d);
      if (pt3) {
        pt = pt3;
      }
    }
    if (children[lt] && (!lt ? (p[cut_dim] - max_d < (*val)[cut_dim]) :
         (p[cut_dim] + max_d >= (*val)[cut_dim]))) {
      Point *pt2 = NULL;
      pt2 = children[lt]->find_nn(p, max_d);
      if (pt2) {
        pt = pt2;
      }
    }
    return pt;
  }
};

KDTree *cache;
int cctr;


void KDTree::init(Point *pts, int start, int end, int cut_dim) {
  this->cut_dim = cut_dim;
  children[0] = children[1] = NULL;
  if (end-start == 1) {
    val = &pts[start]; 
    return;
  }
  int mid = (start+end)/2;
  nth_element(pts+start, pts + mid, pts+end, cmps[cut_dim]);
  while (mid > start && pts[mid-1][cut_dim] == pts[mid][cut_dim]) --mid;
  val = &pts[mid];
  if (mid-start) {
    children[0] = &cache[cctr++];
    children[0]->init(pts, start, mid, cut_dim ^ 1);
  }
  if (end-mid-1) {
    children[1] = &cache[cctr++];
    children[1]->init(pts, mid+1, end, cut_dim ^ 1);
  }
}

struct Cmp2 {
  bool operator()(const Point& p1, const Point& p2) const {
    return p1.idx < p2.idx;
  }
};

int main() {
  setvbuf(stdin, NULL, _IOFBF, 10000);
  setvbuf(stdout, NULL, _IOFBF, 10000);
 
  int n_cases;
  scanf("%d", &n_cases);
  Point *p=  new Point[100024];
  Point *p2 = new Point[100024];
  cache = (KDTree*)malloc(sizeof(KDTree)*100024);
  for (int ctr = 0; ctr < n_cases; ++ctr) {
    cctr=1;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      scanf("%lf%lf", &X(p[i]), &Y(p[i]));
      p[i].idx = i;
    }
    memcpy(p2, p, sizeof(Point)*n);

    cache[0].init(p, 0, n, 0);
    for (int i = 0; i < n; ++i) {
      double d = 1e100;
      Point *pt = cache[0].find_nn(p2[i], d);
      printf("%.0f\n", pow(d,2));
    }
  }
  
  return 0;
}