Pagini recente » Cod sursa (job #2326338) | Cod sursa (job #590264) | Cod sursa (job #370013) | Cod sursa (job #2606826) | Cod sursa (job #980640)
Cod sursa(job #980640)
#include<fstream>
#include<algorithm>
#define oo 200000000
#define NMAX 1000005
#include<cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct point
{
int x , y ;
bool operator< (const point a) const
{
return (x<a.x);
}
}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;
}
long long dist ( point A , point B )
{
return ( A.x -B.x)*(A.x -B.x ) + ( A.y-B.y ) *(A.y -B.y);
}
long long DEI(int st ,int dr)
{
int a,b,x , 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( i != m )
if( real( v[m].x - v[i].x ) < x )
pos[++k] = v[i];
for( i = 1 ; i <= k ; ++i )
for( ii = 1 ; ii <= k ; ++ii )
{
if( i != ii )
{
long long distance = dist ( v[i], v[ii] ) ;
if( distance < x )
x = distance;
}
}
return 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) ;
Answer = DEI(1,N);
g.precision(7);
g<<fixed<<sqrtl (Answer ) ;
}