Cod sursa(job #2970258)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 24 ianuarie 2023 19:27:31
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>
#include <iterator>
#include <math.h>
#define MAXN 100000
#define MAXVAL 1000000000

using namespace std;

struct Point{
  double x;
  double y;
};

long double getDistance(Point p1, Point p2){
  double xdif = p1.x - p2.x;
  double ydif = p1.y - p2.y;
  return sqrt(xdif * xdif + ydif * ydif);
}

bool xComp(Point a, Point b){ // a < b
  return a.x < b.x;
}
bool yComp(Point a, Point b){ // a < b
  return a.y < b.y;
}

set<Point, decltype(yComp)*> s(yComp);
Point p[MAXN];

int main(){
  int n, i, j;
  double min;

  ifstream fin ("cmap.in");
  fin >> n;

  for(i = 0; i < n; i ++){
    fin >> p[i].x >> p[i].y;
  }
  fin.close();

  sort(p, p + n, xComp);

  min = MAXVAL;
  s.insert(p[0]);
  j = 0;

  for(i = 1; i < n; i ++){
    while(p[i].x - p[j].x > min){
      s.erase(p[j]);
      j ++;
    }

    auto lw = s.lower_bound({p[0].x, p[i].y - min});
    while(lw != s.end() && lw->y < p[i].y + min){
      double dist = getDistance(*lw, p[i]);
      if(dist < min)
        min = dist;

      lw ++;
    }

    s.insert(p[i]);
  }

  FILE *fout = fopen("cmap.out", "w");
  fprintf(fout, "%lf\n", min);
  fclose(fout);

  return 0;
}