Cod sursa(job #3297438)

Utilizator Arhiva_Educationala_2Arhiva Educationala doi Arhiva_Educationala_2 Data 22 mai 2025 17:00:17
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>

#include <complex>
#include <random>
#include <vector>
#include <algorithm>

using ftype = double;
using Point = std::complex<ftype>;

int main() {
  FILE *fin = fopen( "cmap.in", "r" );
  FILE *fout = fopen( "cmap.out", "w" );

  std::mt19937 rng(42);

  int n;
  fscanf( fin, "%d", &n );
  std::vector<Point> v;
  for( int i = 0; i < n; i++ ){
    ftype x, y;
    fscanf( fin, "%lf %lf", &x, &y );
    v.emplace_back( x, y );
  }

  Point rot = std::polar( (ftype)1, (ftype)(rng() % 2000) );
  for( auto &P : v ) P *= rot;

  std::sort( v.begin(), v.end(), []( const Point &a, const Point &b ) -> bool {
    return a.real() < b.real();
  } );

  ftype ret = 2e9;
  for( int i = 0; i < n; i++ ){
    for( int j = i + 1; j < n; j++ ){
      if( v[j].real() > v[i].real() + ret )
        break;

      ret = std::min( ret, std::abs( v[i] - v[j] ) );
    }
  }

  fprintf( fout, "%.10lf\n", ret );

  fclose( fin );
  fclose( fout );
  return 0;
}