Cod sursa(job #2500315)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 27 noiembrie 2019 18:40:12
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <bits/stdc++.h>

#define x first
#define y second

const int MAX_N = 100005;
const double INF = 1.0 * MAX_N * MAX_N;

int n;

std::pair <double, double> arr[MAX_N];

bool operator < (const std::pair <double, double> &a,
                 const std::pair <double, double> &b) {
  if (a.x == b.x) {
    return a.y < b.y;
  } else {
    return a.x < b.x;
  }
}

double distance(std::pair <double, double> a,
                std::pair <double, double> b) {
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double dei(int lo, int ri) {
  std::vector <std::pair <double, double>> points;
  double min = INF, lo_ans, ri_ans;
  int len = ri - lo + 1, mid = (lo + ri) >> 1, ri_p, lo_p;
  if (len <= 3) {
    for (int i = lo; i <= ri; ++i) {
      points.push_back(arr[i]);
    }
    for (int i = 0; i < points.size(); ++i) {
      for (int j = i + 1; j < points.size(); ++j) {
        min = std::min(min, distance(points[i], points[j]));
      }
    }
    return min;
  }
  lo_ans = dei(lo, mid);
  ri_ans = dei(mid + 1, ri);
  min = std::min(lo_ans, ri_ans);
  for (int i = lo; i <= ri; ++i) {
    if (abs(arr[mid].x - arr[i].x) <= min) {
      points.push_back(arr[i]);
    }
  }
  for (int i = 0; i < points.size(); ++i) {
    for (int j = i + 1; j < points.size(); ++j) {
      min = std::min(min, distance(arr[i], arr[j]));
    }
  }
  return min;
}

int main() {
  freopen("cmap.in", "r", stdin);
  freopen("cmap.out", "w", stdout);
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    std::cin >> arr[i].x >> arr[i].y;
  }
  std::sort(arr + 1, arr + n + 1);
  std::cout << std::fixed << std::setprecision(6) << dei(1, n);
  return 0;
}