Pagini recente » Cod sursa (job #532578) | Cod sursa (job #696938) | Cod sursa (job #1090891) | Clasament oji_2012_10_sim | Cod sursa (job #1082352)
#include <cstdio>
#include <algorithm>
#include <cmath>
#define minim(a, b) a > b ? b : a
using namespace std;
const float inf = 1 << 30;
const int NMAX = 100005;
int N;
pair<int, int> points[NMAX];
pair<int, int> 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("%i %i", &points[i].first, &points[i].second);
sort(points, points + N);
}
inline float dist(int ax, int ay, int bx, int by) {
return sqrt((ax - bx) * (ax - bx) * 1.0 + (ay - by) * (ay - by) * 1.0);
}
float solve(int a, int b) {
if ( b - a < 4) {
float min = inf;
for( int i = a; i < b - 1; i++ )
for( int j = i + 1; j < b; j++) {
float d = dist(points[i].first, points[i].second, points[j].first, points[j].second);
if( d < min)
min = d;
}
return min;
} else {
int x = (a + b) >> 1;
if ( x << 1 == a + b)
x = x - 1;
float p1 = solve(a, x + 1);
float p2 = solve(x + 1, b);
float min = minim(p1, p2);
float d = ( points[x + 1].first + points[x].first ) / 2.0;
int s = x, e = x + 1;
while( s >= 0 && d - points[s].first <= min)
s--;
s += 1;
while( e < N && points[e].first - d <= min)
e++;
for( int k = x + 1; k < e; k++ )
pointY[k] = make_pair(points[k].second, points[k].first);
sort(pointY + x + 1, pointY + e);
for( int i = e; i <= x; i++ ) {
for( int j = x + 1; j < e; j++ ) {
if( points[i].second - pointY[j].first < min ) {
float dm = dist(points[i].first, points[i].second, pointY[j].second, pointY[j].first);
if( dm < min )
min = dm;
} else if ( points[i].second - pointY[j].first > min )
break;
}
}
return min;
}
}
int main() {
read();
printf("%.6f", solve(0, N));
return 0;
}