Cod sursa(job #2738233)

Utilizator StanSiBranBranSiStan StanSiBran Data 5 aprilie 2021 16:39:40
Problema Cele mai apropiate puncte din plan Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 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;
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++) {
      for (int k = j + 1; k <= dr; k++)
        ans = min(ans, dist(p[j], p[k]));
    }
    sort(cox + st, cox + dr +1);
    return ans;
  }
  int mij = (st + dr) / 2;
  ll best = min(divide(2 * nod, st, mij), divide(2 * nod + 1, mij + 1, dr));
  v.resize(dr - st + 1);
  merge(cox + st, cox + mij + 1, cox + mij + 2, cox + dr + 1, v.begin());
  for (int i = 0; i < v.size(); i++)
    cox[st + i] = v[i];
  int nr = 0;
  for (int i = st; i <= dr; i++)
    if (1ll * (cox[i].y - p[mij].x) * (cox[i].y - p[mij].x) < best)
      a[++nr] = cox[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;
}