Cod sursa(job #1822712)

Utilizator Ionut228Ionut Calofir Ionut228 Data 5 decembrie 2016 14:33:42
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

const long long INF = 9000000000000000000LL;

int n;
vector<pair<long long, long long> > v, w;

long long get_dist(pair<long long, long long> a, pair<long long, long long> b) {
  return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

long long dei(int lt, int rt) {
  if (rt - lt <= 1) {
    return INF;
  } else if (rt - lt == 2) {
    return get_dist(v[lt], v[lt + 1]);
  }

  int mid = (lt + rt) / 2;
  long long sol = min(dei(lt, mid), dei(mid, rt));

  vector<pair<long long, long long> > m(rt - lt + 1), aux;
  merge(w.begin() + lt, w.begin() + mid, w.begin() + mid, w.begin() + rt, m.begin());

  for (vector<pair<long long, long long> >::iterator it = m.begin(); it != m.end(); ++it) {
    if (llabs(it->second - v[mid].first) <= sol) {
      aux.push_back(make_pair(it->second, it->first));
    }
  }

  for (int i = 0; i < aux.size(); ++i) {
    for (int j = i + 1; j < aux.size() && j - i < 8; ++j) {
      sol = min(sol, get_dist(aux[i], aux[j]));
    }
  }

  return sol;
}

int main() {
  fin >> n;
  for (int i = 1; i <= n; ++i) {
    long long x, y;
    fin >> x >> y;
    v.push_back(make_pair(x, y));
  }
  for (int i = 1; i <= n; ++i) {
    w.push_back(make_pair(v[i - 1].second, v[i - 1].first));
  }

  sort(v.begin(), v.end());
  sort(w.begin(), w.end());

  int sol = dei(0, v.size());
  fout << fixed << setprecision(6) << sqrt((double)sol);

  fout << "\n";
  return 0;
}