Pagini recente » Cod sursa (job #1368709) | Cod sursa (job #2944187) | Cod sursa (job #2980100) | Cod sursa (job #3137243) | Cod sursa (job #2984008)
// 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;
#define BUFSIZE 131072
#define BUFM 131071
char ibuf[BUFSIZE];
int ibp = BUFM;
magic_sauce int bgetc(){
if( !(ibp = ((ibp + 1) & BUFM)) )
fread( ibuf, sizeof( char ), BUFSIZE, fin );
return ibuf[ibp];
}
magic_sauce int fgetint(){
int n = 0, ch, semn = 1;
while( isspace( ch = bgetc() ) );
if( ch == '-' ){
semn = -1;
ch = bgetc();
}
do
n = n * 10 + ch - '0';
while( isdigit( ch = bgetc() ) );
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;
}