Pagini recente » Cod sursa (job #940641) | Cod sursa (job #2312655) | Cod sursa (job #235272) | Cod sursa (job #3260113) | Cod sursa (job #579811)
Cod sursa(job #579811)
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;
#define Nmax 100010
struct punct {
int x, y;
} P[Nmax];
int n;
int Poz[Nmax];
double dist (int a, int b) {
return sqrt( (long double) ((long long)(P[a].x - P[b].x) * (long long)(P[a].x - P[b].x) + (long long)(P[a].y - P[b].y) * (long long)(P[a].y - P[b].y)));
}
inline double Min (double a, double b) {
if (a < b) return a;
return b;
}
bool cmp (const int &a, const int &b) {
return P[a].y < P[b].y;
}
bool cmpx (const punct &a, const punct &b) {
return a.x < b.x;
}
double Cmap (int st, int dr) {
if (st == dr) return 0;
double dmin;
if (dr - st + 1 <= 3) {
dmin = dist (st, st + 1);
if (st + 2 == dr) {
dmin = Min (dmin, dist (st + 1, st + 2) );
dmin = Min (dmin, dist (st, st + 2) );
}
return dmin;
}
dmin = Min ( Cmap (st, ((st + dr) >> 1)), Cmap (((st + dr) >> 1) + 1, dr) );
int i, j, N = 0, mij = ((st + dr) >> 1), p;
double d2;
for (i = st; i <= dr; i++)
if ( abs (P[i].x - P[mij].x) <= dmin )
Poz[++N] = i;
sort (Poz + 1, Poz + N + 1, cmp);
for (i = 2, p = 1; i <= N; i++) {
while ( P[ Poz[i] ].y - P[ Poz[p] ].y >= dmin ) p++;
for (j = p; j < i; j++)
dmin = min (dmin, dist (Poz[j], Poz[i]) );
}
return dmin;
}
int main () {
freopen ("cmap.in", "r", stdin);
freopen ("cmap.out", "w", stdout);
scanf ("%d", &n);
for (int i = 1; i <= n; i++)
scanf ("%d %d", &P[i].x, &P[i].y);
sort (P + 1, P + n + 1, cmpx);
printf ("%.6lf\n", Cmap (1, n));
return 0;
}