Cod sursa(job #592629)

Utilizator Addy.Adrian Draghici Addy. Data 29 mai 2011 14:30:24
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define NMAX 100050

struct punct {
	int x, y;
} V[NMAX];

int P[NMAX], n, i;

bool cmpx (punct, punct), cmpy (int, int);
double cmap (int, int);
double dist (int, int);

int main () {

	freopen ("cmap.in", "r", stdin);
	freopen ("cmap.out", "w", stdout);

	scanf ("%d", &n);
	for (i = 1; i <= n; i++)
		scanf ("%d %d", &V[i].x, &V[i].y);

	sort (V + 1, V + 1 + n, cmpx);

	printf ("%.6lf", cmap (1, n));

	return 0;
}

double cmap (int st, int dr) {

	if (st > dr) return 0;

	double dmin;

	if (dr - st + 1 <= 3) {
		dmin = dist (st, st + 1);
		if (dr == st + 2) {
			dmin = min (dmin, dist (st, dr));
			dmin = min (dmin, dist (st + 1, dr));
		}

		return dmin;
	}

	int N = 0, mij = (st + dr) >> 1, p, i, j;

	dmin = min (cmap (st, mij), cmap (mij + 1, dr));

	for (i = st; i <= dr; i++)
		if (abs (V[i].x - V[mij].x) <= dmin)
			P[++N] = i;

	sort (P + 1, P + 1 + N, cmpy);
	for (i = 2, p = 1; i <= N; i++) {
		while (V[ P[i] ].y - V[ P[p] ].y >= dmin) p++;

		for (j = p; j < i; j++)
			dmin = min (dmin, dist (P[j], P[i]));
	}

	return dmin;
}

double dist (int a, int b) {

	double c = V[a].x - V[b].x, d = V[a].y - V[b].y;

	return sqrt (c * c + d * d);
}

bool cmpx (punct a, punct b) {

	return a.x < b.x;
}

bool cmpy (int a, int b) {

	return V[a].y < V[b].y;
}