Cod sursa(job #2913469)

Utilizator avtobusAvtobus avtobus Data 14 iulie 2022 17:48:39
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <algorithm>
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef complex<ld> P;
const ld eps = 1e-7;
int main(void) {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  freopen("cmap.in", "r", stdin);
  freopen("cmap.out", "w", stdout);

  int N;
  cin >> N;
  vector<P> A(N);
  for(int i = 0; i < N; i++) {
    ld x,y;
    cin >> x >> y;
    A[i] = {x,y};
  }
  auto cmpX = [](const P &a, const P &b){return a.real() < b.real(); };
  auto cmpY = [](const P &a, const P &b){return a.imag() < b.imag(); };

  sort(A.begin(), A.end(), cmpX);

  ld res = 2e9;
  auto go = [&](auto self, int l, int r)->void {
    if (r <= l + 3) {
      for(int i = l; i < r; ++i) {
        for(auto j = i+1; j < r; ++j) {
          res = min(res, abs(A[j] - A[i]));
        }
      }
      sort(A.begin() + l, A.begin() + r, cmpY);
      return;
    }
    auto m = (r+l+1)/2;
    ld X = A[m].real();
    self(self, l, m);
    self(self, m, r);
    inplace_merge(A.begin() + l, A.begin() + m, A.begin() + r, cmpY);
    vector<P> buf;
    for(int i = l; i < r; i++) if (abs(A[i].real() - X) < res + eps) {
      buf.push_back(A[i]);
    }
    for(int i = 0; i < (int)buf.size(); i++) {
      for(int j = i+1; j < (int)buf.size() && j < i+8; j++) {
        res = min(res, abs(buf[i] - buf[j]));
      }
    }
  };
  go(go, 0, N);
  cout << std::fixed << setprecision(6) << res << "\n";

  return 0;
}