Cod sursa(job #2836566)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 20 ianuarie 2022 17:01:56
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

const int N = 1e5 + 5;
const double INF = 1e20;

struct Point {
  double x, y;
};

Point v[N];

bool cmp_x(const Point& p1, const Point& p2) {
  return p1.x < p2.x;
}

bool cmp_y(const Point& p1, const Point& p2) {
  return p1.y < p2.y;
}

double calc(int st, int dr) {
  if (dr - st <= 1)
    return INF;
  int m = (st + dr) / 2;
  double l_st = calc(st, m);
  double l_dr = calc(m, dr);
  double l = min(l_st, l_dr);
  double x_sep = v[m].x;
  vector<Point> a;
  for (int i = 0; i < m; ++i)
    if (v[i].x >= x_sep - l)
      a.push_back(v[i]);
  vector<Point> b;
  for (int i = m; i < dr; ++i)
    if (v[i].x <= x_sep + l)
        b.push_back(v[i]);
  sort(a.begin(), a.end(), cmp_y);
  sort(b.begin(), b.end(), cmp_y), cmp_y;
  int pst, pdr;
  pst = pdr = 0;
  double l_fin = l;
  for (auto p: a) {
    while (pdr < b.size() && b[pdr].y <= a[pdr].y + l)
      ++pdr;
    while (pst < b.size() && a[pst].y < a[pdr].y - l)
      ++pst;
    if (pst == b.size())
      break;
    for (int i = pst; i < pdr; ++i)
      l_fin = min(l_fin, (p.x - b[i].x) * (p.x - b[i].x) + (p.y - b[i].y) * (p.y - b[i].y));
  }
  return l_fin;
}

int main() {
  ifstream cin("cmap.in");
  ofstream cout("cmap.out");
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i)
    cin >> v[i].x >> v[i].y;
  cin.close();
  sort(v, v + n, cmp_x);
  cout << fixed << setprecision(6) << sqrt(calc(0, n)) << "\n";
  cout.close();
  return 0;
}