Pagini recente » Cod sursa (job #165531) | Cod sursa (job #2881012) | Cod sursa (job #383320) | Cod sursa (job #1070721) | Cod sursa (job #2049008)
#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;
int n;
koordS p[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 = 99999999;
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 )
{
//cout << gi++ << "\n";
/*/
if( l + 4 > r )
{
return kevesPontCucc( l, r );
}
//*/
//*/
if( l >= r - 1 )
return 99999999;
else if( r - l <= 3 )
{
//return dist( p[l], p[r] );
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:
vector< koordS > y;
/*/
for( int i = m; i < n && abs( p[i].x - p[m].x ) <= s; ++i )
{
if( abs( p[i].x - p[m].x ) < s )
y.push_back( p[i] );
}
for( int i = m - 1; i >= 0 && abs( p[i].x - p[m].x ) <= s; --i )
{
if( abs( p[i].x - p[m].x ) < s )
y.push_back( p[i] );
}
//*/
for( int i = 0; i < n; ++i )
if( abs( p[i].x - p[m].x ) <= s )
y.push_back( p[i] );
sort( y.begin(), y.end(), compary );
//cout << y.size() << "\n";
ld hres = 99999999;
for( int i = 0; i < y.size(); ++i )//abs( p[j].y - p[i].y ) <= s
{
for( int j = i + 1; j - i < 8 && j < y.size(); ++j )
{
ld ds = dist( p[i], p[j] );
if( ds < hres )
hres = ds;
}
}
// cout << " " << hres << "\n";
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 );
fcout << "\n";
/*/
for( int i = 0; i < n; ++i )
{
cout << p[i].x << " " << p[i].y << "\n";
}//*/
return 0;
}