Cod sursa(job #2972484)

Utilizator vladburacBurac Vlad vladburac Data 29 ianuarie 2023 16:13:44
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;

ifstream fin( "cmap.in" );
ofstream fout( "cmap.out" );

struct Point{
  int x;
  int y;
};
Point points[NMAX+1];

double dist( Point a, Point b ) {
  return sqrt( 1LL * abs( a.x - b.x ) * abs( a.x - b.x ) + 1LL * abs( a.y - b.y ) * abs( a.y - b.y ) );
}

bool cmp( Point a, Point b ) {
  return ( a.x < b.x ) || ( a.x == b.x && a.y < b.y );
}

inline bool operator <( const Point& a, const Point& b ) {
  return ( a.y < b.y ) || ( a.y == b.y && a.x < b.x );
}

set<Point> activePoints;

int main() {
  int n, i, j;
  double minDist;
  fin >> n;
  for( i = 0; i < n; i++ ) {
    fin >> points[i].x >> points[i].y;
  }
  sort( points, points + n, cmp );
  activePoints.insert( points[0] );
  j = 0;
  minDist = DBL_MAX;
  for( i = 1; i < n; i++ ) {
    while( j < i && points[i].x - points[j].x > minDist ) {
      activePoints.erase( points[j] );
      j++;
    }
    auto it = activePoints.lower_bound( { INT_MIN, points[i].y - minDist } );
    while( it != activePoints.end() && abs( (*it).y - points[i].y ) <= minDist ) {
      minDist = min( minDist, dist( *it, points[i] ) );
      it++;
    }
    activePoints.insert( points[i] );
  }
  fout << fixed << setprecision( 6 );
  fout << minDist;
  return 0;
}