Cod sursa(job #409102)

Utilizator katakunaCazacu Alexandru katakuna Data 3 martie 2010 14:08:56
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
using namespace std;

#define Nmax 100010
#define INF 1000000010

struct punct {int x, y;} Px[Nmax], Py[Nmax];
int n, i, Ny, mij, p, j;
int poz[Nmax];

int cmp_x (int a, int b) {
	return Px[a].x < Px[b].x;
}

int cmp_y (punct a, punct b) {
	return a.y < b.y;
}

double dist (double x1, double y1, double x2, double y2) {
	return sqrt ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double Dmin (int st, int dr) {
	
	double dmin = INF, d; 
	if (dr - st + 1 <= 3) {
		if (dr - st + 1 >= 2)
			dmin = dist ( Px[ poz[st] ].x, Px[ poz[st] ].y, Px[ poz[st + 1] ].x, Px[ poz[st + 1] ].y );
		
		if (dr - st + 1 == 3) {
			d = dist ( Px[ poz[st] ].x, Px[ poz[st] ].y, Px[ poz[st + 2] ].x, Px[ poz[st + 2] ].y );
			if (d < dmin) dmin = d;
			
			d = dist ( Px[ poz[st + 2] ].x, Px[ poz[st + 2] ].y, Px[ poz[st + 1] ].x, Px[ poz[st + 1] ].y );
			if (d < dmin) dmin = d;
		}
		
		return dmin;
	}
	
	dmin = Dmin (st, (dr + st) >> 1);
	d = Dmin (((dr + st) >> 1) + 1, dr);
	if (d < dmin) dmin = d;
	
	mij = (st + dr) >> 1; Ny = 0;
	for (i = st; i <= dr; i++) 
		if ( abs (Px[poz[mij]].x - Px[poz[i]].x) <= dmin ) 
			Py[++Ny] = Px[poz[i]];
	
	sort (Py + 1, Py + Ny + 1, cmp_y);
	for (i = 2, p = 1; i <= Ny; i++) {
		while (Py[i].y - Py[p].y > dmin) 
			p++;
		
		for (j = p; j < i; j++) {
			d = dist (Py[i].x, Py[i].y, Py[j].x, Py[j].y);
			if (d < dmin) dmin = d;
		}
	}
	
	return dmin;
}

int main () {

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

	scanf ("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf ("%d %d", &Px[i].x, &Px[i].y);
		poz[i] = i;
	}
	
	sort (poz + 1, poz + n + 1, cmp_x);
	
	printf ("%.6lf", Dmin (1, n));
	
	return 0;
}