Pagini recente » Cod sursa (job #2902226) | Cod sursa (job #2269220) | Cod sursa (job #546226) | Cod sursa (job #1586662) | Cod sursa (job #980805)
Cod sursa(job #980805)
#include<fstream>
#include<algorithm>
#define oo (1LL<<62)
#define NMAX 1000005
#include<cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct point
{
long long x , y ;
}v[NMAX];
int N;
point pos[NMAX];
int k = 0 ;
inline long long real ( long long A )
{
if( A < 0 )
return -A ;
else
return A;
}
inline long long dist ( point A , point B )
{
return real ( ( A.x - B.x) ) *real ( ( A.x -B.x) ) + real ( ( A.y-B.y ) ) *real ( ( A.y-B.y ) );
}
bool comp ( point A , point B )
{
return A.y < B.y;
}
long long DEI(int st ,int dr)
{
long long a,b;
long long x ;
int i , ii;
int m = (st + dr ) / 2;
if(st >= dr )
return oo;
if( dr-st==1 )
return dist(v[st],v[dr]);
a=DEI( st , m ) ;
b=DEI( m + 1 , dr ) ;
x=min(a,b);
k = 0 ;
for( i = st ; i <= dr ; ++i )
if( real(v[m].x - v[i].x) < x )
pos[++k] = v[i];
sort( pos +1 , pos + k +1 , comp );
for( i = 1 ; i <= k ; ++i )
for( ii = i+1 ; ii <= i+8 && ii <= k ; ++ii )
x = min(x,dist ( v[i], v[ii] )) ;
return x ;
}
bool cmp ( point A , point B )
{
return A.x < B.x ;
}
int main ( void )
{
int i ;
long long Answer ;
f>>N;
for( i = 1 ; i <= N ; ++i )
f>>v[i].x>>v[i].y;
sort(v+1,v+N+1 ,cmp) ;
Answer = DEI(1,N);
g.precision(7);
g<<fixed<<sqrtl(Answer ) ;
}