Closest Pair

 struct Point {
    long long x;
    long long y;
};
struct ClosestPair
{
public:
  int N;
  vector<int> tmpt;
  vector<Point> point;
  ClosestPair(int N){
    this->N = N;
    tmpt.resize(N + 1);
    point.resize(N + 1);
  }
 

  bool cmpxy(const Point& a, const Point& b) {
    if (a.x != b.x)
      return a.x < b.x;
    return a.y < b.y;
  }

  bool cmpy(const int& a, const int& b) {
    return point[a].y < point[b].y;
  }

  long long dis2(int i, int j) {
    return (point[i].x - point[j].x) * (point[i].x - point[j].x)
        + (point[i].y - point[j].y) * (point[i].y - point[j].y);
  }

  long long sqr(long long x) {
    return x * x;
  }

  long long Closest_Pair(int left, int right) {
    long long d = LLONG_MAX;
    if (left == right)
      return d;
    if (left + 1 == right)
      return dis2(left, right);
    int mid = (left + right) >> 1;
    long long d1 = Closest_Pair(left, mid);
    long long d2 = Closest_Pair(mid + 1, right);
    d = min(d1, d2);
    int i, j, k = 0;
    for (i = left; i <= right; i++) {
      if (sqr(point[mid].x - point[i].x) <= d)
        tmpt[k++] = i;
    }
    sort(begin(tmpt), begin(tmpt) + k, cmpy);
    for (i = 0; i < k; i++) {
      for (j = i + 1; j < k && sqr(point[tmpt[j]].y - point[tmpt[i]].y) < d;
          j++) {
        long long d3 = dis2(tmpt[i], tmpt[j]);
        if (d > d3)
          d = d3;
      }
    }
    return d;
}
};