Pagini recente » Cod sursa (job #2731812) | Cod sursa (job #1058076) | Cod sursa (job #1583596) | Cod sursa (job #1077858) | Cod sursa (job #1371585)
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define MAXN 100005
#define INF 1LL<<61
FILE *f=fopen("cmap.in","r"), *g=fopen("cmap.out","w");
using namespace std;
struct Puncte{
long long int x, y;
} X[MAXN], Y[MAXN], t[MAXN], sir[MAXN];
// X = sortat dupa X
// Y = sortat dupa Y (se va afla prin interclasare)
// t = ajutor pentru interclasare
// sir = doar cele care sunt la distanta <= solutia momentana
long long int N;
bool cmp( Puncte A, Puncte B ){
if( A.x < B.x || ( A.x == B.x && A.y < B.y ) ) return 1;
return 0;
}
long long int Distanta( Puncte A, Puncte B ){
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
void Citire(){
long long int i;
fscanf(f,"%lld\n",&N);
for(i=1;i<=N;i++)
fscanf(f,"%lld %lld\n",&X[i].x,&X[i].y);
sort(X+1,X+N+1,cmp);
}
void Interclaseaza( long long int k1, long long int mij, long long int k2 ){
long long int i, j, k;
i = k1; k = k1-1; j = mij+1;
while( i<=mij && j<=k2 )
if( Y[i].y < Y[j].y ) t[++k] = Y[i++];
else t[++k] = Y[j++];
while( i<=mij ) t[++k] = Y[i++];
while( j<=k2 ) t[++k] = Y[j++];
for(i=k1;i<=k2;i++) Y[i] = t[i];
}
long long int DMIN( long long int k1, long long int k2 ){
long long int dmin, i, j, mij, Lsir;
if( k2-k1+1 <= 3 ){ // Mai putin de 3 puncte
for(i=k1;i<=k2;i++) Y[i] = X[i];
for(i=k1;i<k2;i++) // Sortare dupa Y
for(j=i+1;j<=k2;j++)
if( Y[i].y > Y[j].y ) swap( Y[i], Y[j] );
if( k1 == k2 ) return INF;
dmin = Distanta( X[k1], X[k1+1] );
for(i=k1;i<k2;i++) // Distantele dintre cele 2 sau 3 puncte
for(j=i+1;j<=k2;j++)
dmin = min( Distanta( X[i], X[j] ), dmin );
return dmin;
}
mij = (k1+k2)/2;
dmin = min( DMIN(k1,mij), DMIN(mij+1,k2) );
Interclaseaza( k1, mij, k2 );
Lsir = 0;
for(i=k1;i<=k2;i++)
if( abs( Y[i].x - Y[mij].x ) <= dmin ) sir[++Lsir] = Y[i];
for(i=1;i<=Lsir;i++)
for(j=1; j<=7 && i+j <= Lsir; j++)
dmin = min( Distanta(sir[i],sir[i+j]) , dmin );
return dmin;
}
int main(){
Citire();
fprintf(g,"%.6lf\n", sqrt( DMIN(1,N) ) );
return 0;
}