Pagini recente » Cod sursa (job #783855) | Cod sursa (job #2142633) | Cod sursa (job #2204004) | Cod sursa (job #1960101) | Cod sursa (job #2048975)
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#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 );
}
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] );
}
sort( y.begin(), y.end(), compary );
ld hres = 99999999;
for( int i = 0; i < y.size(); ++i )
{
for( int j = i + 1; abs( p[j].y - p[i].y ) < s; ++j )
{
ld ds = dist( p[j], p[i] );
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 << solve( 0, n - 1 );
fcout << "\n";
/*/
for( int i = 0; i < n; ++i )
{
cout << p[i].x << " " << p[i].y << "\n";
}//*/
return 0;
}