Pagini recente » Cod sursa (job #338857) | Cod sursa (job #1065863) | Cod sursa (job #2312864) | Cod sursa (job #1536931) | Cod sursa (job #2067639)
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
#define Nmax 100010
#define Inf 1<<30
struct punct
{
int x, y;
}v[Nmax],w[Nmax];
int n;
int cmp (punct a, punct b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
double dist ( punct a, punct b)
{
double difx = a.x - b.x;
double dify = a.y - b.y;
return sqrt ( difx * difx + dify * dify ) ;
}
double divide ( int st, int dr)
{
if ( dr-st < 3 )
{
double D, Dmin=Inf;
int i, j;
for(i = st; i < dr; i++)
for(j = i + 1 ; j <= dr; j++)
{
D = dist( v[i] , v[j] );
if(D < Dmin)
Dmin = D;
}
return Dmin;
}
int m=( st + dr ) / 2;
int d = v[m].x;
double S1 = divide ( st, m ) ;
double S2 = divide ( m+1, dr ) ;
double S = S1;
if(S2 < S1)
S = S2;
int i,j = m+1 ,k=0;
for(i = st; i <= m; i++)
if( abs(v[i].x - d) <= S ) break;
while( i <= m && j <= dr && abs(v[j].x - d) <= S )
if( v[i].y < v[j].y )
w[++k]=v[i++];
else
w[++k]=v[j++];
while ( i <= m )
w[++k]=v[i++];
while ( j <= dr && abs(v[j].x-d) <= S )
w[++k]=v[j++];
double D, Dmin=Inf;
for(i = 1; i < k ; i++)
for(j = i + 1 ; j <= (i+7) && j <= k; j++)
{
D = dist(w[i],w[j]);
if(D < Dmin)
Dmin=D;
}
if(Dmin>S)
Dmin=S;
return Dmin;
}
int main()
{
int n;
f >> n;
for ( int i = 1; i <= n ;i++)
f >> v[i].x >> v[i].y;
sort(v+1,v+n+1,cmp);
g << fixed << setprecision(6) << divide(1,n);
return 0;
}