Pagini recente » Cod sursa (job #1076152) | Cod sursa (job #634629) | Cod sursa (job #3257277) | Cod sursa (job #2701596) | Cod sursa (job #2917320)
// Program de Mircea Rebengiuc
// inceput pe 2021.11.19
// reluat pe 2022.08.04
// facut din ce imi mai aduc aminte din clasa 7
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#define MAXN 100000
#define INF 2000000000.0
int x[MAXN];
int y[MAXN];
// vectori de puncte auxiliari pentru
// selectarea punctelor interesante
// si pentru mergesort
int auxx[MAXN];
int auxy[MAXN];
static inline double getDist( int x1, int x2, int y1, int y2 ){
return sqrtl(
((long long)(x1 - x2)) * (x1 - x2) +
((long long)(y1 - y2)) * (y1 - y2)
);
}
static inline double mind( double a, double b ){
return a < b ? a : b;
}
void myqsort( int begin, int end ){
int b = begin - 1, e = end + 1, p = x[(begin + end) / 2], aux;
while( x[++b] < p );
while( x[--e] > p );
while( b < e ){
aux = x[b];
x[b] = x[e];
x[e] = aux;
aux = y[b];
y[b] = y[e];
y[e] = aux;
while( x[++b] < p );
while( x[--e] > p );
}
if( begin < e )
myqsort( begin, e );
if( e + 1 < end )
myqsort( e + 1, end );
}
double minDist( int st, int dr ){
int mij = (st + dr) / 2, i, j1, j2, j, split;
int auxmij, auxn;
double min_st_dr, retval;
if( st == dr )
return INF;
if( st + 1 == dr )// daca fac toata chestia doar pentru 2 puncte irosesc timpul
return getDist( x[st], x[dr], y[st], y[dr] );
// la inceput [st, dr] este sortat dupa x
split = x[mij];
retval = min_st_dr = mind( minDist( st, mij ), minDist( mij + 1, dr ) );
// acum [st, mij] si [mij + 1, dr] sunt sortate dupa y, nu dupa x
// luam numai punctele la distanta mai mica decat min_st_dr de split pentru ca daca sunt mai departate
// inseamna ca nu au cum sa aiba o distanta mai mica decat cea curenta cu un punct din partea opusa
j = 0;// indicile curent in auxx[] si auxy[]
for( i = st ; i <= mij ; i++ )
if( split - x[i] < min_st_dr ){
auxx[j] = x[i];
auxy[j] = y[i];
j++;
}
auxmij = j;
for( i = mij + 1 ; i <= dr ; i++ )
if( x[i] - split < min_st_dr ){
auxx[j] = x[i];
auxy[j] = y[i];
j++;
}
auxn = j;
// tinem intervalul [j1, j2] de puncte din partea dreapta care sunt la distanta <= min_st_dr pe y fata de i
// pot fi maxim 6 puncte in intervalul [j1, j2] pentru ca distanta minima dintre doua puncte din partea
// dreapta este >= min_st_dr inseamna ca
j1 = j2 = auxmij;
for( i = 0 ; i < auxmij ; i++ ){
while( j1 < auxn && auxy[j1] + min_st_dr < auxy[i] )// j1 is inclusive
j1++;
while( j2 < auxn && auxy[j2] - min_st_dr <= auxy[i] )// j2 is exclusive
j2++;
for( j = j1 ; j < j2 ; j++ )
retval = mind( retval, getDist( auxx[i], auxx[j], auxy[i], auxy[j] ) );
}
// tot ce mai trebuie sa facem e sa dam merge la cele doua jumatati
for( i = st ; i <= dr ; i++ ){
auxx[i] = x[i];
auxy[i] = y[i];
}
i = st;
j = mij+1;
j1 = st;// j1 is the output index
while( i <= mij && j <= dr ){
if( auxy[i] < auxy[j] ){
x[j1] = auxx[i];
y[j1++] = auxy[i++];
}else{
x[j1] = auxx[j];
y[j1++] = auxy[j++];
}
}
while( i <= mij ){
x[j1] = auxx[i];
y[j1++] = auxy[i++];
}
while( j <= dr ){
x[j1] = auxx[j];
y[j1++] = auxy[j++];
}
return retval;
}
FILE *fin, *fout;
static inline 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" );
int n, i;
n = fgetint();
for( i = 0 ; i < n ; i++ ){
x[i] = fgetint();
y[i] = fgetint();
}
myqsort( 0, n - 1 );
fprintf( fout, "%lf\n", minDist( 0, n - 1 ) );
fclose( fin);
fclose( fout);
return 0;
}