Cod sursa(job #2969172)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 22 ianuarie 2023 17:29:28
Problema Cele mai apropiate puncte din plan Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

#define N_MAX 100000
#define INF 2000000000

struct point {
  int x, y;
};

bool cmp_x(const point& a, const point& b) {
  return a.x < b.x;
}

double dist(const point& a, const point& b) {
  return sqrt((double)(a.x - b.x) * (a.x - b.x) + (double)(a.y - b.y) * (a.y - b.y));
}

point v[N_MAX + 1];

struct cmp_y {
  bool operator()(const int& a, const int& b) {
    return v[a].y < v[b].y;
  }
};

int main() {
  FILE *fin, *fout;
  int n, i;
  double min_dist;

  fin = fopen("cmap.in", "r");

  fscanf(fin, "%d", &n);
  for(i = 0; i < n; i++)
    fscanf(fin, "%d%d", &v[i].x, &v[i].y);

  fclose(fin);

  sort(v, v + n, cmp_x);

  set<int, cmp_y> s;

  s.insert(0);
  min_dist = INF;

  for(i = 1; i < n; i++) {
    for(auto j = s.begin(); j != s.end(); j++) {
      if(v[*j].x < v[i].x - min_dist)
        j = s.erase(j);
    }

    v[n] = {-INF, v[i].y - min_dist};
    auto it = s.lower_bound(n);

    for(;it != s.end() && v[*it].y <= v[i].y + min_dist; it++)
      min_dist = min(min_dist, dist(v[i], v[*it]));

    s.insert(i);
  }

  fout = fopen("cmap.out", "w");
  fprintf(fout, "%hf", min_dist);
  fclose(fout);
  return 0;
}