Cod sursa(job #3361725)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 28 iulie 2026 00:36:39
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.8 kb
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <random>
#include <iomanip>

#define debug(x) #x << " = " << x << '\n'
using ll = long long;
using ld = long double;

std::mt19937 rng(123);

struct Point {
  int x, y;
  Point() {}
  Point(int _x, int _y) : x(_x), y(_y) {}

  bool operator == (const Point &other) const {
    return x == other.x && y == other.y;
  }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        std::size_t h1 = std::hash<int>{}(p.x);
        std::size_t h2 = std::hash<int>{}(p.y);        
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

std::unordered_map<Point, std::vector<Point>, PointHash> mp;

ll dist_sq(Point A, Point B) {
  return (ll) (A.x - B.x) * (A.x - B.x) + (ll) (A.y - B.y) * (A.y - B.y);
}
ld dist(Point A, Point B) {
  return std::sqrt(dist_sq(A, B));
}

const int dx[8] = {-1, 0, +1, 0, -1, -1, +1, +1};
const int dy[8] = {0, -1, 0, +1, -1, +1, -1, +1};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);

  #ifdef INFOARENA
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
  #endif

  int n;
  std::cin >> n;

  std::vector<Point> a(n);
  std::vector<int> ord(n);
  for (int i = 0; i < n; i++) {
    ord[i] = i;
  }
  std::shuffle(ord.begin(), ord.end(), rng);

  for (int i = 0; i < n; i++) {
    std::cin >> a[ord[i]].x >> a[ord[i]].y;
  }
  for (auto &[x, y] : a) {
    x += 1e9, y += 1e9;
  }
  
  ld answer = 2e9;

  // for (int i = 0; i < n; i++) {
  //   Point P = Point(a[i].x / D, a[i].y / D);
  //   if (!mp.count(P)) {
  //     mp[P] = a[i];
  //     continue;
  //   }
  //   answer = std::min(answer, dist(a[i], mp[P]));
  //   D = std::round(answer);
  //   mp.clear();
  //   for (int j = 0; j <= i; j++) {
  //     Point P = Point(a[j].x / D, a[j].y / D);
  //     mp[P] = a[j];
  //   }
  // }

  for (int repeat = 0; repeat < 20 * n + 1000; repeat++) {
    int i = rng() % n, j = rng() % n;
    if (i != j) {
      answer = std::min(answer, dist(a[i], a[j]));
    }
  }

  ll D = std::ceil(answer);

  for (int i = 0; i < n; i++) {
    Point P(a[i].x / D, a[i].y / D);
    mp[P].push_back(a[i]);
  }
  
  for (const auto &[P, A] : mp) {
    auto [x, y] = P;
    for (int dir = 0; dir < 8; dir++) {
      int xx = x + dx[dir], yy = y + dy[dir];
      if (mp.count({xx, yy})) {
        const auto &B = mp[{xx, yy}];
        for (const auto &a : A) {
          for (const auto &b : B) {
            answer = std::min(answer, dist(a, b));
            D = std::round(answer);
          }
        }
      }
    }
  }
  
  std::cout << std::fixed << std::setprecision(6) << answer;
  
  return 0;
}