Cod sursa(job #2956574)

Utilizator nicu_ducalNicu Ducal nicu_ducal Data 19 decembrie 2022 20:18:52
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.45 kb
#include <bits/stdc++.h>
using namespace std;

template <typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template <typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
using i64 = long long int;

const int INF = INT_MAX, MOD = 1e9 + 7;
const long long LINF = 2e18;
const double EPS = 1e-9, PI = acos(-1);
const int dx[] = {0, 0, 0, -1, 1, -1, 1, 1, -1};
const int dy[] = {0, -1, 1, 0, 0, -1, 1, -1, 1};

i64 distance(pair<i64, i64> &a, pair<i64, i64> &b) {
  return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

i64 divide(int lo, int hi, vector<pair<i64, i64>> &points, vector<pair<i64, i64>> &ord_points) {
  i64 mini = LINF;
  if (lo >= hi) return mini;
  else if (hi - lo <= 3) {
    for (int i = lo; i < hi; i++)
      for (int j = i + 1; j <= hi; j++)
        mini = min(mini, distance(points[i], points[j]));
    return mini;
  }

  int mid = lo + (hi - lo) / 2;
  mini = min(divide(lo, mid, points, ord_points), divide(mid + 1, hi, points, ord_points));
  vector<pair<i64, i64>> merged(hi - lo + 1);
  merge(ord_points.begin() + lo, ord_points.begin() + mid + 1, ord_points.begin() + mid + 1, ord_points.begin() + hi + 1, merged.begin());
  copy(merged.begin(), merged.end(), ord_points.begin() + lo);

  vector<pair<i64, i64>> potential;
  for (int i = lo; i <= hi; i++) {
    i64 cur = (ord_points[i].second - points[mid].first) * (ord_points[i].second - points[mid].first);
    if (cur <= mini)
      potential.push_back(ord_points[i]);
  }
  for (int i = 0; i < (int) potential.size(); i++) {
    for (int j = i + 1; j < (int) potential.size(); j++)
      mini = min(mini, distance(potential[i], potential[j]));
  }

  return mini;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  /// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

  ifstream cin("cmap.in");
  ofstream cout("cmap.out");

  int N; cin >> N;
  vector<pair<i64, i64>> points(N), ord_points;
  for (auto &point: points)
    cin >> point.first >> point.second;
  sort(points.begin(), points.end());
  for (auto &point: points)
    ord_points.emplace_back(point.second, point.first);

  i64 ans = divide(0, (int) points.size() - 1, points, ord_points);
  cout << fixed << setprecision(7) << sqrt(ans) << "\n";
  return 0;
}