Cod sursa(job #2725891)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 19 martie 2021 20:08:46
Problema Cele mai apropiate puncte din plan Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cmath>
#include <cstdio>
#include <random>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long double ld;
const int N = (int) 1e5 + 7;
int n;

struct point {
  ld x, y;
} p[N];

bool cmp(point a, point b) {
  return a.x < b.x;
}

ld dist(point a, point b) {
  ld dx = a.x - b.x, dy = a.y - b.y;
  return dx * dx + dy * dy;
}

mt19937 rng((long long) (new char));

int main() {
  freopen ("cmap.in", "r", stdin);
  freopen ("cmap.out", "w", stdout);

  ld shift = rng();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    p[i] = {a, b};
    ld r = sqrt(p[i].x * p[i].x + p[i].y * p[i].y), ang = atan2(p[i].y, p[i].x) + shift;
    p[i].x = r * cos(ang);
    p[i].y = r * sin(ang);
  }
  sort(p + 1, p + n + 1, cmp);
  ld cur = (ld) 1e18 + 7;
  for (int i = 2; i <= n; i++) {
    for (int j = i - 1; j >= 1; j--) {
      if (p[i].x - p[j].x > cur) {
        break;
      }
      cur = min(cur, dist(p[i], p[j]));
    }
  }
  cout << fixed << setprecision(6) << sqrt(cur) << "\n";
}