Cod sursa(job #2920010)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 21 august 2022 15:35:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#include <ctype.h>

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

using cmplx = std::complex<double>;

bool cmp ( cmplx a, cmplx b ){
  if( a.real() != b.real() )
    return a.real() < b.real();
  return a.imag() < b.imag();
}

double operator ^ ( cmplx a, cmplx b ){
  return std::abs( a - b );
}

#define MAXN 200000

cmplx v[MAXN];

FILE *fin, *fout;

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

  std::mt19937 rng( clock() );
  int n, i, j;
  cmplx rot = std::polar( 1.0, 2e-3 * std::arg( cmplx{ -1, 0 } ) * (rng() % 1000) );
  double mind = 2e9;

  fscanf( fin, "%d", &n );
  for( i = 0 ; i < n ; i++ ){
    double x, y;
    fscanf( fin, "%lf%lf", &x, &y );
    v[i] = rot * cmplx{ x, y };
  }

  std::sort( v, v + n, cmp );

  for( i = 0 ; i < n ; i++ ){
    j = i + 1;
    while( j < n && v[j].real() - v[i].real() < mind )
      mind = std::min( mind, v[i] ^ v[j++] );
  }

  fprintf( fout, "%.6lf\n", mind );

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