Cod sursa(job #2913517)

Utilizator avtobusAvtobus avtobus Data 14 iulie 2022 21:34:52
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <algorithm>
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef complex<ll> P;
ll square(ll x) { return x*x; }
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(auto &p: A) {
    ll x,y;
    cin >> x >> y;
    p = {x,y};
  }

  sort(A.begin(), A.end(), [](const P &a, const P &b){ return a.real() < b.real(); });
  ll res = 1e9 * 2ll * 1e9;
  auto go = [&](auto self, int l, int r)->void{
    if (r <= l+3) {
      for(int i = l; i < r; ++i) {
        for(int j = i+1; j < r; ++j) {
          res = min(res, norm(A[i]- A[j]));
        }
      }
      sort(A.begin() + l, A.begin() + r, [](const P &a, const P &b){ return a.imag() < b.imag(); });
      return;
    }
    int m = (r+l+1)/2;
    ll X = A[m].real();
    self(self, l, m);
    self(self, m, r);
    inplace_merge(A.begin() + l, A.begin() + m, A.begin() + r, [](const P &a, const P &b){
      return a.imag() < b.imag();
    });
    {
      vector<int> buffer(8);
      for(int i = l, buf_start = 0, buf_end = 0; true;) {
        while(i < r && buf_end < buf_start + 8) {
          if (square(A[i].real() - X) <= res) {
            buffer[buf_end & 7] = i;
            buf_end++;
          }

          i++;
        }
        for(int ti = buf_start + 1; ti < buf_end; ti++) {
          res = min(res, norm(A[buffer[buf_start & 7]] - A[buffer[ti & 7]]));
        }
        buf_start++;
        if (buf_start >= buf_end) break;
      }
    }
  };
  go(go, 0, N);
  cout << fixed << setprecision(6) << sqrt(res) << "\n";

  return 0;
}