Cod sursa(job #2984002)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 23 februarie 2023 13:16:38
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
// This program was written
// by Mircea Rebengiuc
// for problem cmap
// on 23.02.2023

#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <random>

#define magic_sauce inline __attribute__((always_inline))
using ftype = double;

template<typename T> magic_sauce T min( T a, T b ){ return a < b ? a : b; }

const int MAXN = 1e5;

struct Point {
  ftype x, y;
} p[MAXN + 1];

#define dist( a, b ) (sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)))

void myqsort( int begin, int end ){
  int b = begin - 1, e = end + 1;
  ftype piv = p[(begin + end) >> 1].x;
  Point aux;

  while( p[++b].x < piv );
  while( p[--e].x > piv );

  while( b < e ){
    aux = p[b];
    p[b] = p[e];
    p[e] = aux;
    
    while( p[++b].x < piv );
    while( p[--e].x > piv );
  }

  if( begin < e )
    myqsort( begin, e );
  if( e + 1 < end )
    myqsort( e + 1, end );
}

FILE *fin, *fout;

magic_sauce int fgetint(){
  int n = 0, ch, semn = 1;

  while( isspace( ch = fgetc( fin ) ) );
  if( ch == '-' ){
    semn = -1;
    ch = fgetc( fin );
  }
  do
    n = n * 10 + ch - '0';
  while( isdigit( ch = fgetc( fin ) ) );

  return n * semn;
}

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

  std::mt19937 rng;
  rng.seed( clock() );
  ftype teta = 4e-3 * atan( 1 ) * (rng() & 1023);
  ftype a = cos( teta ), b = -sin( teta ), c = sin( teta ), d = cos( teta ); // rotation matrix

  int n, i, j;
  ftype auxx, auxy;
  ftype ans = 1e10;

  n = fgetint();

  for( i = 0 ; i < n ; i++ ){
    auxx = fgetint();
    auxy = fgetint();
    p[i].x = a * auxx + b * auxy;
    p[i].y = c * auxx + d * auxy;
  }

  myqsort( 0, n - 1 );
  p[n].x = 2e10;
  for( i = 0 ; i < n ; i++ ){
    j = i + 1;
    while( p[j].x - p[i].x < ans ){
      ans = min( ans, dist( p[i], p[j] ) );
      j++;
    }
  }

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

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