Cod sursa(job #552626)

Utilizator BuRNB Radu BuRN Data 12 martie 2011 17:16:54
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
using namespace std;

#define nmax 100001

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

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

punct D;

ofstream out("cmap.out");
void citire()
{
	ifstream in("cmap.in"); in>>n;
	for(long i=1; i<=n; i++)
		in>>p[i].x>>p[i].y;
}

void afisare()
{
	freopen("date.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 calc_dist(long pi, long ps)
{
	double dt;
	for(long i=pi; i<ps; i++)
		for(long j=i+1; j<=ps; j++)
		{
			dt = euclid(i, j);
			if(dt < S)
				S = dt;
		}
}

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 wtf(int l, int r)
{
	double best;
	if(r-l <= 2)
	{
		best = euclid(l, l+1);
		if(r-l == 2)
			best = min(best, min(euclid(l,r), euclid(l+1, r)) );
	}
}

void solve()
{
	sort(p+1, p+1+n, cmpx); // sortat abscisa
	d_coord(); // coord. dreptei D
	wtf(1, n);
	//calc_dist(1, mij); calc_dist(mij+1, n); // minimul din stanga si dreapta
	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;
}