Pagini recente » Cod sursa (job #2305245) | Cod sursa (job #204323) | Cod sursa (job #1901623) | Cod sursa (job #2126767) | Cod sursa (job #2663510)
#include <bits/stdc++.h>
#define se second
#define fi first
#define ll long long
#define pll pair<long long,long long>
#define mp make_pair
using namespace std;
ifstream f ( "cmap.in" );
ofstream g ( "cmap.out" );
const int MAX_N = 100005;
const ll INF = 4e18;
vector < pll> V ( MAX_N ), X, Y;
ll dist ( const pll& a, const pll& b )
{
return ( a.fi - b.fi ) * ( a.fi - b.fi ) + ( a.se - b.se ) * ( a.se - b.se );
}
ll go ( int st, int dr, vector <pll >& X, vector < pll >& Y )
{
if ( st >= dr - 1 )
return INF;
else
if ( dr - st == 2 )
{
if ( Y[st] > Y[st + 1] )
swap ( Y[st], Y[st + 1] );
return dist ( X[st], X[st + 1] );
}
int mid = ( st + dr ) / 2;
ll best = min ( go ( st, mid, X, Y ), go ( mid, dr, X, Y ) );
merge ( Y.begin() + st, Y.begin() + mid, Y.begin() + mid, Y.begin() + dr, V.begin() );/// se face intreclasarea elem din Ps si celor din Pd
copy ( V.begin(), V.begin() + ( dr - st ), Y.begin() + st );
int v_size = 0;
for ( int i = st; i < dr; ++ i )
if ( abs ( Y[i].second - X[mid].first ) <= best )
V[v_size ++] = Y[i];
for ( int i = 0; i < v_size - 1; ++ i )
{
for ( int j = i + 1; j < v_size && j - i < 8; ++ j )
best = min ( best, dist ( V[i], V[j] ) );
}
return best;
}
int main ()
{
int n;
f >> n;
X.resize ( n ), Y.resize ( n );
for ( int i = 0; i < n; ++ i )
f >> X[i].fi >> X[i].se;
sort ( X.begin(), X.end() );
for ( int i = 0; i < n; ++ i )
Y[i] = mp ( X[i].se, X[i].fi );
g << fixed << setprecision ( 6 ) << sqrt ( go ( 0, X.size(), X, Y ) ) << "\n";
return 0;
}