Cod sursa(job #3211866)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 10 martie 2024 15:57:23
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;

struct Point {
  int x, y;
} v[5 + nmax];

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

bool cmpx(Point a, Point b) {
  return a.x < b.x;
}

bool cmpy(Point a, Point b) {
  return a.y < b.y;
}

long long solve(int left, int right) {
  if (left == right)
    return INT_MAX;
  int middle = (left + right) / 2, xmid = v[(left + right) / 2].x;
  long long mdist = min(solve(left, middle), solve(middle + 1, right));
  vector<Point> p;
  for (int i = left; i <= right; i++)
    if (1ll * (xmid - v[i].x) * (xmid - v[i].x) <= mdist)
      p.push_back(v[i]);
  sort(p.begin(), p.end(), cmpy);
  for (int i = 0; i < (int)p.size(); i++)
    for (int j = i + 1; j < (int)p.size(); j++) {
      if (1ll * (p[j].y - p[i].y) * (p[j].y - p[i].y) > mdist)
        break;
      mdist = min(mdist, dist(p[i], p[j]));
    }
  return mdist;
}

int main() {
  ifstream fin("cmap.in");
  ofstream fout("cmap.out");
  int n;
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> v[i].x >> v[i].y;
  sort(v + 1, v + n + 1, cmpx);
  long double ans = sqrt((long double)solve(1, n));
  fout << fixed << setprecision(6) << ans << '\n'; 
  return 0;
}