Cod sursa(job #1996579)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 1 iulie 2017 23:06:20
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long LL;

#ifdef INFOARENA
#define ProblemName "cmap"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

const int MAXN = 100010;
pair<int, int> v[MAXN];
int auxv[MAXN], avsz;
int N;

LL dst(int i, int j) {
  int dx = v[i].first - v[j].first;
  int dy = v[i].second - v[j].second;
  return 1LL * dx * dx + 1LL * dy * dy;
}

LL brute(int left, int right) {
  LL res = LLONG_MAX;
  for (int i = left; i < right; ++i)
  for (int j = i + 1; j < right; ++j)
    res = min(res, dst(i, j));
  return res;
}

bool smallerY(pair<int, int> p1, pair<int, int> p2) {
  if (p1.second != p2.second) return p1.second < p2.second;
  return p1.first < p2.first;
}

LL cmap(int left, int right) {
  int L = right - left;
  if (L <= 3) {
    sort(v + left, v + right, smallerY);
    return brute(left, right);
  }
  int mid = left + L / 2;
  LL delta = min(cmap(left, mid), cmap(mid, right));
  inplace_merge(v + left, v + mid, v + right, smallerY);
  avsz = 0;
  for (int i = left; i < right; ++i) {
    if (1LL * v[i].first * v[i].first > delta) continue;
    auxv[avsz++] = i;
  }
  LL best = delta;
  for (int ii = 0; ii < avsz; ++ii) {
    int lim = min(avsz, ii + 10);
    for (int j = ii + 1; j < lim; ++j)
      best = min(best, dst(auxv[ii], auxv[j]));
  }
  return best;
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  scanf("%d", &N);
  for (int i = 0; i < N; ++i)
    scanf("%d%d", &v[i].first, &v[i].second);
  sort(v, v + N);
  printf("%.8lf\n", sqrt(cmap(0, N)));
  return 0;
}