Pagini recente » Cod sursa (job #3198277) | Cod sursa (job #2031720) | Cod sursa (job #83793) | Cod sursa (job #812668) | Cod sursa (job #2049101)
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
#define ll long long
#define ld long double
using namespace std;
struct koordS
{
ll x, y;
};
bool myfunction (int i,int j) { return (i<j); }
bool compar( koordS k1, koordS k2 )
{
return k1.x < k2.x;
}
bool compary( koordS k1, koordS k2 )
{
return k1.y < k2.y;
}
const int NLIM = 1e5 + 10;
const long double INF = 4e18;
int n;
koordS p[NLIM];
koordS y[NLIM];
ld dist( koordS p1, koordS p2 )
{
return sqrt( (p1.x - p2.x)*(p1.x - p2.x) + ( p1.y - p2.y )*( p1.y - p2.y ) );
}
ld kevesPontCucc( int l, int r )
{
ld res = INF;
for( int i = l; i < r; ++i )
for( int j = i + 1; j <= r; ++j )
{
ld d = dist( p[i], p[j] );
if( d < res )
res = d;
}
return res;
}
int gi = 0;
ld solve( int l, int r )
{
//*/
if( r - l <= 30 )
{
return kevesPontCucc( l, r );
}
//*/
int m = ( l + r ) / 2;
ld lr = solve( l, m );
ld rr = solve( m + 1, r );
ld s = min( lr, rr );
// combine:
int ysize = 0;
for( int i = m; i < r && abs( p[i].x - p[m].x ) <= s; ++i )
if( abs( p[i].x - p[m].x ) < s )
y[ysize++] = p[i];
for( int i = m - 1; i >= l && abs( p[i].y - p[m].x ) <= s; --i )
if( abs( p[i].x - p[m].x ) < s )
y[ysize++] = p[i];
sort( y, y + ysize, compary );
//cout << ysize << "\n";
ld hres = INF;
for( int i = 0; i < ysize; ++i )//abs( p[j].y - p[i].y ) <= s //j - i < 8
for( int j = i + 1; abs( p[j].y - p[i].y ) <= s && j < ysize; ++j )
{
ld ds = dist( p[i], p[j] );
if( ds < hres )
hres = ds;
}
return min( hres, s );
}
ifstream fcin("cmap.in");
ofstream fcout("cmap.out");
int main()
{
fcin >> n;
for( int i = 0; i < n; ++i )
fcin >> p[i].x >> p[i].y;
sort( p, p + n, compar );
fcout << fixed << setprecision(6) << solve( 0, n ) << "\n";
/*/
for( int i = 0; i < n; ++i )
{
cout << p[i].x << " " << p[i].y << "\n";
}//*/
return 0;
}