Pagini recente » Cod sursa (job #1763148) | Cod sursa (job #2138974) | Cod sursa (job #2233223) | Cod sursa (job #1493969) | Cod sursa (job #980844)
Cod sursa(job #980844)
#include<fstream>
#include<algorithm>
#define oo (4e18)
#define NMAX 100005
#include<cmath>
#define x first
#define y second
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
typedef pair < int , int > point ;
pair < int , int > v[NMAX] ;
int N;
pair < int , int > pos[NMAX];
int k;
inline long long dist ( point A , point B )
{
long long b = (A.x-B.x);
b *= b;
long long a = ( A.y-B.y ) ;
a *= a;
return a + b;
}
bool comp ( point A , point B )
{
return A.y < B.y;
}
long long DEI(int st ,int dr)
{
int m = (st + dr ) / 2;
if(st >= dr )
return oo;
if( dr-st==1 )
return dist(v[st],v[dr]);
long long x = min ( DEI ( st , m ) , DEI( m + 1 , dr ) ) ;
int i , ii;
k = 0 ;
for( i = st ; i <= dr ; ++i )
if( abs(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 ) ;
}