Cod sursa(job #2500395)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 27 noiembrie 2019 20:13:41
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>

#define ll long long

const int MAX_N = 100005;
const long long INF = 2e18;

int n;

std::vector <std::pair <long long, long long>> arr;

long long square(long long value) {
  return 1LL * value * value;
}

long long distance(std::pair <long long, long long> a,
                   std::pair <long long, long long> b) {
  return (square(a.first - b.first) + square(a.second - b.second));
}

long long solve(long long lo, long long ri) {
  long long ans = INF, mid = (lo + ri) >> 1;
  std::vector <std::pair <long long, long long>> points;
  if (ri - lo + 1 <= 3) {
    for (int i = lo; i <= ri; ++i) {
      points.push_back(arr[i]);
    }
    for (int i = 0; i < points.size(); ++i) {
      for (int j = 1 + i; j < points.size(); ++j) {
        ans = std::min(ans, distance(points[i], points[j]));
      }
    }
    return ans;
  }
  ans = std::min(solve(lo, (lo + ri) / 2), solve((lo + ri) / 2 + 1, ri));
  for (int i = lo; i <= ri; ++i) {
    if (abs(arr[i].first - arr[mid].first) <= ans) {
      points.push_back(arr[i]);
    }
  }
  std::sort(points.begin(), points.end());
  for (int i = 0; i < points.size(); ++i) {
    for (int j = 1 + i; j < points.size() && j - i < 8; ++j) {
      ans = std::min(ans, distance(points[i], points[j]));
    }
  }
  return ans;
}

int main() {
  long long x, y;
  freopen("cmap.in", "r", stdin);
  freopen("cmap.out", "w", stdout);
  std::cin >> n;
  for (int i = 0; i < n; ++i) {
    std::cin >> x >> y;
    arr.push_back(std::make_pair(x, y));
  }
  std::sort(arr.begin(), arr.end());
  std::cout << std::fixed << std::setprecision(6) << sqrt(1.0 * solve(0, n - 1));
  return 0;
}