Pagini recente » Cod sursa (job #1358910) | Cod sursa (job #2589442) | Cod sursa (job #1771305) | Cod sursa (job #1404915) | Cod sursa (job #1082607)
#include <cstdio>
#include <algorithm>
#include <cmath>
typedef long long ll;
#define minim(a, b) a > b ? b : a
using namespace std;
const double inf = 1 << 30;
const int NMAX = 100005;
int N;
pair<ll, ll> points[NMAX];
pair<ll, ll> pointY[NMAX];
void read() {
freopen( "cmap.in", "r", stdin );
freopen( "cmap.out", "w", stdout );
scanf("%i", &N);
for( int i = 0; i < N; i++ )
scanf("%lld %lld", &points[i].first, &points[i].second);
sort(points, points + N);
}
inline double dist(pair<ll, ll> a, pair<ll, ll> b) {
return sqrt((a.first - b.first) * (a.first - b.first) * 1.0 + (a.second - b.second) * (a.second - b.second) * 1.0);
}
double solve(int a, int b) {
if ( b - a < 3) {
double min = inf;
for( int i = a; i < b; i++ )
for( int j = i + 1; j <= b; j++) {
double d = dist(points[i], points[j]);
if( d < min)
min = d;
}
return min;
} else {
ll x = (a + b) >> 1;
double p1 = solve(a, x);
double p2 = solve(x + 1, b);
double min = minim(p1, p2);
double d = ( points[x + 1].first + points[x].first ) / 2.0;
int s = x, e = x + 1;
while( s >= a && d - points[s].first <= min )
s--;
s += 1;
while( e <= b && points[e].first - d <= min)
e++;
for( int k = s; k < e; k++ )
pointY[k] = make_pair(points[k].second, points[k].first);
sort(pointY + s, pointY + e);
for( int i = s; i < e - 1; i++ )
for( int j = i + 1; j < e && j - i < 5; j++ ) {
double d = dist(pointY[i], pointY[j]);
min = minim(min, d);
}
return min;
}
}
int main() {
read();
printf("%.6lf", solve(0, N - 1));
return 0;
}