Cod sursa(job #1489818)

Utilizator salam1Florin Salam salam1 Data 22 septembrie 2015 04:30:35
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int NMAX = 100505;
const long long INF = (1LL << 62);

struct pt {
  int x, y;

  bool operator < (const pt& other) const {
    if (x < other.x) return true;
    if (x > other.x) return false;
    return y < other.y;
  }
};
int n, cnt;
pt A[NMAX], sortedY[NMAX], auxY[NMAX], special[NMAX];

void read() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &A[i].x, &A[i].y);
  }
}

inline long long dist(pt& a, pt& b) {
  return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}

long long closest(int l, int r) {
  if (l == r) {
    return INF;
  }
  if (r - l == 1) {
    return dist(A[l], A[r]);
  }

  int mid = (l + r) >> 1;
  long long best = min(closest(l, mid), closest(mid + 1, r));

  // merge
  merge(sortedY + l, sortedY + mid + 1, sortedY + mid + 1, sortedY + r + 1, auxY + l);
  copy(auxY + l, auxY + r + 1, sortedY + l);

  cnt = 0;
  for (int i = l; i <= r; i++)
    if (1LL * (sortedY[i].x - A[mid].x) * (sortedY[i].x - A[mid].x) <= best) {
      special[++cnt] = sortedY[i];
    }

  for (int i = 1; i <= cnt; i++)
    for (int j = i + 1; j <= i + 7 && j <= cnt; j++) {
      best = min(best, dist(special[i], special[j]));
    }

  return best;
}

int main() {
  freopen("cmap.in", "r", stdin);
  freopen("cmap.out", "w", stdout);

  read();
  sort(A + 1, A + n + 1);
  copy(A + 1, A + n + 1, sortedY + 1);

  long long res = closest(1, n);
  printf("%.10lf\n", sqrt((double)res));
  return 0;
}