Pagini recente » Cod sursa (job #1535399) | Cod sursa (job #1631297) | Cod sursa (job #990246) | Cod sursa (job #902958) | Cod sursa (job #2414409)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#define NMAX 100000
#define x first
#define y second
#define pint pair<int, int>
using namespace std;
ifstream fin ( "cmap.in" );
ofstream fout ( "cmap.out" );
pint v[1 + NMAX], p[1 + NMAX];
double minim ( double a, double b ) {
return ( a < b ) ? a : b;
}
double dist ( pint a, pint b ) {
return sqrt ( ( double ) ( a.x - b.x ) * ( a.x - b.x ) + ( double ) ( a.y - b.y ) * ( a.y - b.y ) );
}
double cmp ( pint a, pint b ) {
return a.y < b.y;
}
double sol ( int st, int dr ) {
if ( dr - st + 1 <= 3 ) {
sort ( v + st, v + dr + 1, cmp );
double ans = INFINITY;
for ( int i = st; i <= dr; ++ i )
for ( int j = i + 1; j <= dr; ++ j )
ans = minim ( ans, dist ( v[i], v[j] ) );
return ans;
}
int mid = ( st + dr ) / 2;
int xmid = v[mid].x;
double ans = minim ( sol ( st, mid ), sol ( mid + 1, dr ) );
int ind = st;
int i = st, j = mid + 1;
while ( i <= mid && j <= dr ) {
if ( v[i].y < v[j].y )
p[ind ++] = v[i ++];
else
p[ind ++] = v[j ++];
}
for ( ; i <= mid; ++ i ) p[ind ++] = v[i];
for ( ; j <= dr; ++ j ) p[ind ++] = v[j];
for ( int i = st; i <= dr; ++ i )
v[i] = p[i];
ind = 0;
for ( int i = st; i <= dr; ++ i )
if ( fabs ( v[i].x - xmid ) < ans )
p[ind++] = v[i];
for ( int i = 0; i < ind; ++ i )
for ( int j = i + 1; j <= i + 7 && j < ind; ++ j )
ans = min ( ans, dist ( p[i], p[j] ) );
return ans;
}
int main() {
int N;
fin >> N;
for ( int i = 1; i <= N; ++i )
fin >> v[i].x >> v[i].y;
fout << setprecision(8) << fixed;
sort( v + 1, v + N + 1 );
fout << sol (1, N);
return 0;
}