Pagini recente » Cod sursa (job #1254354) | Cod sursa (job #2234294) | Cod sursa (job #2264095) | Cod sursa (job #2829991) | Cod sursa (job #2280525)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int Nmax = 100002;
struct Point
{
int x,y;
} A[Nmax] , B[Nmax] , C[Nmax ];
bool CompX( Point a , Point b )
{ return a.x<b.x; }
bool CompY ( Point a , Point b)
{ return a.y<b.y; }
long long Distance ( Point a , Point b)
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
long long Solve ( int left , int right )
{
if ( right - left + 1 <= 3 )
{
sort ( A + left , A + right + 1 , CompY );
long long LeastDist = ( (long long)A[left].x - (long long ) A[left+1].x ) * ( (long long)A[left].x - (long long ) A[left+1].x ) + ( (long long)A[left].y - (long long ) A[left+1].y ) * ( (long long)A[left].y - (long long ) A[left+1].y );
for ( int i=left ; i < right ; ++i)
for( int j=i+1 ; j<=right ;++j)
{ long long Dist = ( (long long)A[i].x - (long long ) A[j].x ) * ( (long long)A[i].x - (long long ) A[j].x ) + ( (long long)A[i].y - (long long ) A[j].y ) * ( (long long)A[i].y - (long long ) A[j].y ) ;
if ( LeastDist > Dist )
LeastDist = Dist ;
}
return LeastDist;
}
else
{
int Middle = (left + right ) / 2;
Point Mid;
Mid.x = A[Middle].x;
Mid .y = 0 ;
long long LeastDist1 = Solve ( left , Middle ) ;
long long LeastDist2 = Solve ( Middle + 1 , right ) ;
long long LeastDist = min(LeastDist1 , LeastDist2 );
int i ,j ,k = 0 , h = 0;
for ( i = left , j =Middle +1 ; i<= Middle || j<=right ; )
if ( i<=Middle && ( ( A[i].y < A[j].y ) || j > right ) )
B[ ++k ] = A[ i++] ;
else if ( j<=right )
B[++k] = A[j++];
for (i=1 , j = left ;i<=k && j<= right ;++i ,++j)
{if ( Distance( Mid , B[i] ) <= LeastDist )
C[++h] = B[i];
A[j]=B[i];
}
for (i=1; i< h;++i)
for (j=i+1;j<=i+7;++j)
{ long long Dist = Distance(C[i],C[j]);
if ( Dist < LeastDist )
LeastDist = Dist ;
}
return LeastDist;
}
return 0;
}
int main()
{
int N ;
long long result ;
fin>>N;
for ( int i = 1; i <= N ; ++i )
fin>>A[i].x>>A[i].y;
sort(A+1,A+N+1,CompX);
result = Solve( 1 , N );
fout<< setprecision(6) << fixed <<sqrt ( (double) result) ;
return 0;
}