Cod sursa(job #2836550)

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

using namespace std;

const double INF = 1e20;

struct Point {
  double x, y;
};

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(vector<Point> v) {
  if (v.size() <= 1)
    return INF;
  double l_st = calc(vector<Point>(v.begin(), v.begin() + v.size() / 2));
  double l_dr = calc(vector<Point>(v.begin() + v.size() / 2, v.end()));
  double l = min(l_st, l_dr);
  double x_sep = v[v.size() / 2].x;
  vector<Point> a;
  for (int i = 0; i < v.size() / 2; ++i)
    if (v[i].x >= x_sep - l)
      a.push_back(v[i]);
  vector<Point> b;
  for (int i = v.size() / 2; i < v.size(); ++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 st, dr;
  st = dr = 0;
  double l_fin = l;
  for (auto p: a) {
    while (dr < b.size() && b[dr].y <= a[dr].y + l)
      ++dr;
    while (st < b.size() && a[st].y < a[dr].y - l)
      ++st;
    if (st == b.size())
      break;
    for (int i = st; i < dr; ++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;
  vector<Point> p;
  for (int i = 0; i < n; ++i) {
    double x, y;
    cin >> x >> y;
    p.push_back({x, y});
  }
  cin.close();
  sort(p.begin(), p.end(), cmp_x);
  cout << fixed << setprecision(6) << sqrt(calc(p)) << "\n";
  cout.close();
  return 0;
}