Cod sursa(job #2058529)

Utilizator SmarandaMaria Pandele Smaranda Data 5 noiembrie 2017 19:05:49
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>

using namespace std;

struct Point{
  int x, y;
};

const double inf = 2000000000.0;

double dist(const Point &A, const Point &B) {
  return sqrt((1.0 * A.x - B.x) * (A.x - B.x) + (1.0 * A.y - B.y) * (A.y - B.y));
}

double solve_median(int m, double d, int l, int r, vector<Point> &p) {
  vector<Point> v;

  for (int i = m; i >= l; --i)
    if (p[m].x - d >= p[i].x)
      v.push_back(p[i]);
  for (int i = m; i <= r; ++i)
    if (p[m].x + d >= p[i].x)
      v.push_back(p[i]);
  sort(v.begin(), v.end(), [](const Point &A, const Point &B) -> bool {
        return A.y < B.y;
      });
  for (int i = 0; i < v.size(); ++i)
    for (int j = i + 1; j <= v.size() && j <= i + 5; ++j) {
      d = min(d, dist(v[i], v[j]));
    }
  return d;
}

double solve(int l, int r, vector<Point> &p) {
  if (l >= r)
    return inf;
  if (r - l + 1 == 2)
    return dist(p[l], p[r]);
  int m = (l + r) / 2;
  double min_left = solve(l, m, p);
  double min_right = solve(m + 1, r, p);
  double d = min(min_left, min_right);
  d = min(d, solve_median(m, d, l, r, p));
  return d;
}

int main() {
  ifstream cin("cmap.in");
  ofstream cout("cmap.out");
  
  int n;
  cin >> n;
  vector<Point> p(n);
  for (int i = 0; i < n; ++i)
    cin >> p[i].x >> p[i].y;
  sort(p.begin(), p.end(), [](const Point &A, const Point &B) -> bool {
        return A.x < B.x;
      });
  double ans = solve(0, n - 1, p);
  cout << fixed << setprecision(6) << ans << "\n";
  return 0;
}