Cod sursa(job #2738224)

Utilizator StanSiBranBranSiStan StanSiBran Data 5 aprilie 2021 16:26:38
Problema Cele mai apropiate puncte din plan Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int, int>
#define ll long long
 
using namespace std;
 
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const int N = 1e6 + 1;
 
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");

pii p[100002], cox[100002];

ll dist (pii a, pii b) {
  return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y);
}

vector<pii>v[(1 << 18) + 2];
pii a[100002];

int n, x, y;

ll divide (int nod, int st, int dr) {
  if (dr - st + 1 <= 3) {
    ll ans = INF;
    for (int j = st; j <= dr; j++) {
      v[nod].push_back(cox[j]);
      for (int k = j + 1; k <= dr; k++)
        ans = min(ans, dist(p[j], p[k]));
    }
    sort(v[nod].begin(), v[nod].end());
    return ans;
  }
  int mij = (st + dr) / 2;
  ll best = min(divide(2 * nod, st, mij), divide(2 * nod + 1, mij + 1, dr));
  v[nod].resize(dr - st + 1);
  merge(v[2 * nod].begin(), v[2 * nod].end(), v[2 * nod + 1].begin(), v[2 * nod + 1].end(), v[nod].begin());
  v[2 * nod].clear();
  v[2 * nod + 1].clear();
  int nr = 0;
  for (int i = 0; i < v[nod].size(); i++)
    if (1ll * (v[nod][i].x - p[mij].x) * (v[nod][i].x - p[mij].x) < best)
      a[++nr] = v[nod][i];
  for (int i = 1; i <= nr; i++)
    for (int j = max(1, i - 7); j <= i - 1; j++)
      best = min(best, dist(a[i], a[j]));
  return best;
}

int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> p[i].x >> p[i].y;
  sort(p + 1, p + n + 1);
  for (int i = 1; i <= n; i++)
    cox[i] = {p[i].second, p[i].first};
  fout << fixed << setprecision(10) << sqrt((double)divide(1, 1, n)) << "\n";
  return 0;
}