Cod sursa(job #2797252)

Utilizator PetyAlexandru Peticaru Pety Data 9 noiembrie 2021 17:09:23
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const ll MOD = 1e9 + 7;
const ll INF = 1e9;

ifstream fin ("cmap.in");
ofstream fout ("cmap.out");


int n;
struct point {
  ll x,y;
  bool operator < (const point &a) {
    if (x == a.x)
      return y < a.y;
    return x < a.x;
  }
} p[100002], inv[100002], a[100002];

ll dist (point a, point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
vector<point>v;


ll divide (int st, int dr) {
  if (dr - st + 1 <= 3) {      
    ll ans = INF;
    for (int i = st; i <= dr; i++)
      for (int j = i + 1; j <= dr; j++)
        ans = min(ans, dist(p[i], p[j]));
    return ans;
  }
  int mid = (st + dr) / 2;
  ll best = min(divide(st, mid), divide(mid + 1, dr));
  v.resize(dr - st + 1);
  merge(inv + st, inv + mid + 1, inv + mid + 1, inv + dr + 1, v.begin());
  for (int i = st; i <= dr; i++)
    inv[i] = v[i - st];
  int nr = 0;
  for (int i = st; i <= dr; i++)
    if ((inv[i].y - p[mid].x) * (inv[i].y - p[mid].x) < best)
      a[++nr] = inv[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()
{
//   ios_base::sync_with_stdio(false);
//   cin.tie(0); cout.tie(0);
  fin >> n;
  for (int i = 1; i <= n; i++) {
    int x, y;
    fin >> p[i].x >> p[i].y;
  }
  sort(p + 1, p + n + 1);
  for (int i = 1; i <= n; i++)
    inv[i] = {p[i].y, p[i].x};
  fout << fixed << setprecision(10) << sqrt((double)divide(1, n)) << "\n";
  return 0;
}