Cod sursa(job #2725902)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 19 martie 2021 20:23:24
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cmath>
#include <cstdio>
#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;
}

ld cur = (ld) 1e18 + 7;

void rec(int l, int r) {
  if (l == r) return;
  int m = (l + r) / 2;
  rec(l, m);
  rec(m + 1, r);
  for (int j = m + 1; j <= r; j++) {
    bool este = 0;
    for (int k = m; k >= l; k--) {
      if ((p[j].x - p[k].x) * (p[j].x - p[k].x) > cur) break;
      este = 1;
      cur = min(cur, dist(p[j], p[k]));
    }
    if (!este) {
      break;
    }
  }
}

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

  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) + 123;
    p[i].x = r * cos(ang);
    p[i].y = r * sin(ang);
  }
  sort(p + 1, p + n + 1, cmp);
  rec(1, n);

  cout << fixed << setprecision(6) << sqrt(cur) << "\n";
}