Pagini recente » Cod sursa (job #2123713) | Cod sursa (job #2296522) | Cod sursa (job #3203998) | Cod sursa (job #2952103)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#define x first
#define y second
using namespace std;
using ull = unsigned long long;
const int nmax = 1e5;
const ull oo = 1e18;
pair < int, int > v[nmax + 1], rev[nmax + 1];
vector < pair < int, int > > srt;
pair < int, int > a[nmax + 1];
ull dist ( pair < int, int > a, pair < int, int > b ) {
return ( ull ) ( a.x - b.x ) * ( a.x - b.x ) +
( ull ) ( a.y - b.y ) * ( a.y - b.y );
}
ull divide ( int st, int dr ) {
if ( dr - st + 1 <= 3 ) {
ull best = oo;
for ( int i = st; i < dr; i++ )
for ( int j = i + 1; j <= dr; j++ )
best = min ( best, dist ( v[i], v[j] ) );
sort ( rev + st, rev + dr );
return best;
}
int mij = ( st + dr ) / 2;
ull best = min ( divide ( st, mij ), divide ( mij + 1, dr ) );
srt.resize ( dr - st + 1 );
merge ( rev + st, rev + mij + 1,
rev + mij + 1, rev + dr + 1,
srt.begin () );
for ( int i = 0; i < srt.size (); i++ )
rev[i + st] = srt[i];
int nr = 0;
for ( int i = st; i <= dr; i++ )
if ( abs ( rev[i].y - v[mij].x ) <= best )
a[nr++] = rev[i];
for ( int i = 0; i < nr; i++)
for ( int j = max ( 0, i - 7 ); j < i; j++)
best = min ( best, dist ( a[i], a[j] ) );
return best;
}
ifstream fin ( "cmap.in" );
ofstream fout ( "cmap.out" );
int main() {
int n;
fin >> n;
for ( int i = 0; i < n; i++ )
fin >> v[i].x >> v[i].y;
sort ( v, v + n );
for ( int i = 0; i < n; i++ )
rev[i] = { v[i].second, v[i].first };
fout << fixed << setprecision ( 6 ) << sqrt ( divide ( 0, n - 1 ) );
return 0;
}