I1_mine.cpp

#include<cstdio>
#include<vector>
#include<algorithm>
#include<climits>
#define INF LONG_MAX
#define MAX 1000000
using namespace std;

struct point {
  long long x, y;

  point(long long _x, long long _y) {
    x = _x; y = _y;
  }
};

int Z, n;
long long result;
vector<point> points;
vector<point> points_temp;

void load_data_and_cleaning();
void calculate();
void print_data();

int main(int argc, const char *argv[]) {
  scanf("%d", &Z);
  while(Z--) {
    load_data_and_cleaning();
    calculate();
    print_data();
  }
  return 0;
}

void load_data_and_cleaning() {
  long long x, y;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%lld %lld", &x, &y);
    points.push_back(point(x, y));
  }
}

bool comp_x(point a, point b) {
  return a.x < b.x;
}

bool comp_y(point a, point b) {
  return a.y < b.y;
}

long long distance_mine(point a, point b) {
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

long long smallest_distance(long long p, long long q) {
  long long d, d1, d2, center, s;

  if (p == q) return INF;
  if (p + 1 == q) return distance_mine(points[p], points[q]);

  center = (p + q)/2;
  d1 = smallest_distance(p, center);
  d2 = smallest_distance(center, q);
  d = min(d1, d2);
  s = points[center].x;

  for (int i = p; i <= q; i++)
    if ((s - points[i].x)*(s - points[i].x) < d) 
      points_temp.push_back(points[i]);

  sort(points_temp.begin(), points_temp.end(), comp_y);

  for (int i = 0; i < points_temp.size(); i++) 
    for (int j = i + 1; j < i + 7 && j < points_temp.size(); j++)
      d = min(d, distance_mine(points_temp[i], points_temp[j]));
 
  points_temp.clear();

  return d;
}

void calculate() {
  sort(points.begin(), points.end(), comp_x);
  result = smallest_distance(0, n-1);
}

void print_data() {
  printf("%lld\n", result);
}