Cod sursa(job #552639)

Utilizator BuRNB Radu BuRN Data 12 martie 2011 17:31:33
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

#define nmax 100001

long n, mij, q;
double S = 1000000000;

struct punct
{
	long x, y;
}p[nmax], pp[nmax];

punct D;

void citire()
{
	freopen("cmap.in","r",stdin); scanf("%ld", &n);
	for(long i=1; i<=n; i++)
		scanf("%ld %ld", &p[i].x, &p[i].y);
}

void afisare()
{
	freopen("cmap.out","w",stdout);
	printf("%.6lf", S);
}

bool cmpx(punct a, punct b)
{
	return a.x < b.x;
}

bool cmpy(punct a, punct b)
{
	return a.y < b.y;
}

void d_coord()
{
	mij = n/2;
	D.x = p[mij].x;
}

double euclid(long i, long j)
{
	return sqrt( pow(p[i].x-p[j].x, double(2)) + pow(p[i].y-p[j].y, double(2)) );
}

void det_int()
{
	for(long i=1; i<=n; i++)
		if(p[i].x <= D.x+S && p[i].x >= D.x-S)
			pp[++q] = p[i];
	sort(pp+1, pp+1+q, cmpy);
}

void solve()
{
	sort(p+1, p+1+n, cmpx); // sortat abscisa
	d_coord(); // coord. dreptei D
	det_int(); // punctele din intervalul 2*S
	double dt;
	for(long i=1; i<=q; i++)
		for(long j=i+1; j<=i+7 && j<=q; j++)
		{
			dt = euclid(i, j);
			if(dt < S)
				S = dt;
		}
}

int main()
{
	citire();
	solve();
	afisare();
	return 0;
}