Cod sursa(job #3361715)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 28 iulie 2026 00:21:22
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 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, 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[4] = {-1, 0, +1, 0};
const int dy[4] = {0, -1, 0, +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;
  ll D = std::round(answer);

  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 (const auto &[P, A] : mp) {
    auto [x, y] = P;
    for (int dir = 0; dir < 4; dir++) {
      int xx = x + dx[dir], yy = y + dy[dir];
      if (mp.count({xx, yy})) {
        answer = std::min(answer, dist(A, mp[{xx, yy}]));
      }
    }
  }
  
  std::cout << std::fixed << std::setprecision(6) << answer;
  
  return 0;
}