closestpoint.cc

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

template<typename T>
struct p2d {
  T x, y;
  p2d(T x = 0, T y = 0) : x(x), y(y) {}
  p2d(const p2d &a) : x(a.x), y(a.y) {}
  p2d operator - (const p2d &a) const {
    return p2d(x-a.x, y-a.y);
  }
  p2d operator + (const p2d &a) const {
    return p2d(x+a.x, y+a.y);
  }
  void operator -= (const p2d &a) {
    x -= a.x, y -= a.y;
  }
  void operator += (const p2d &a) {
    x += a.x, y += a.y;
  }
  bool operator == (const p2d &a) const {
    return x == a.x and y == a.y;
  }
  bool operator != (const p2d &a) const {
    return x != a.x or y != a.y;
  }

  T norm2() const {
    return x * x + y * y;
  }
  T norm() const {
    return sqrt(norm2());
  }
};

template<typename T>
T dist(const p2d<T> &a, const p2d<T> &b) {
  return (a-b).norm();
}

typedef p2d<double> pt;
typedef pair<int, int> pii;

struct ClosestPair {
  const vector<pt> &P;
  ClosestPair(const vector<pt> &P) : P(P) { }

  double center(const vector<size_t> &V, double x, double d, pii &ans) {
    vector<size_t> S;
    for (size_t id : V)
      if (P[id].x > x-d and P[id].x < x+d)
        S.push_back(id);
    double r = 1e300, t;
    for (size_t i = 0; i < S.size(); ++i)
      for (size_t j = i + 1; j < S.size() and P[S[j]].y - P[S[i]].y < d; ++j)
        if ((t = dist(P[S[j]], P[S[i]])) < r) {
          r = t;
          ans = {S[i], S[j]};
        }
    return r;
  }

  double recu(const vector<size_t> &H, const vector<size_t> &V, pii &ans) {
    const size_t n = H.size();
    if (n <= 1)
      return 1e300;
    const size_t m = n >> 1;
    vector<bool> left(n);
    vector<size_t> vert, T(n), hori;
    vert.reserve(m);
    hori.reserve(m);
    for (size_t i = 0; i < m; ++i)
      left[H[i]] = true;
    int j = 0;
    for (size_t i = 0; i < n; ++i)
      if (left[i]) {
        vert.push_back(V[i]);
        T[i] = j++;
      }
    for (size_t i = 0; i < m; ++i)
      hori.push_back(T[H[i]]);
    pii pl, pr, pc;
    double dl = recu(hori, vert, pl);
    vert.clear();
    vert.reserve(n-m);
    hori.clear();
    hori.reserve(n-m);
    j = 0;
    for (size_t i = 0; i < n; ++i)
      if (not left[i]) {
        vert.push_back(V[i]);
        T[i] = j++;
      }
    for (size_t i = m; i < n; ++i)
      hori.push_back(T[H[i]]);
    double dr = recu(hori, vert, pr), d = min(dl, dr);
    double dc = center(V, P[V[H[m]]].x, d, pc);
    return min(d, dc);
  }

  double calc(pii &ans) {
    const size_t n = P.size();
    vector<size_t> vert(n), hori(n), T(n);
    for (size_t i = 0; i < n; ++i)
      hori[i] = vert[i] = i;
    sort(vert.begin(), vert.end(), [&](size_t i, size_t j) {
        return P[i].y < P[j].y; });
    for (size_t i = 0; i < n; ++i)
      T[vert[i]] = i;
    sort(hori.begin(), hori.end(), [&](size_t i, size_t j) {
        return P[i].x < P[j].x; });
    for (size_t i = 0; i < n; ++i)
      hori[i] = T[hori[i]];
    return recu(hori, vert, ans);
  }
};

int main() {
  int n, x, y;
  cin >> n;
  vector<pt> P;
  P.reserve(n);
  for (int i = 0; i < n; ++i) {
    cin >> x >> y;
    P.push_back(pt(x, y));
  }
  pii p;
  cout << ClosestPair(P).calc(p) << endl;
}