Cod sursa(job #487514)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 25 septembrie 2010 14:03:41
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 100001;

struct punct
{
	int x,y;
};

punct a[N],o[N]; int n;
punct Y[N]; int nY;

inline double min(double a, double b)
{
	return (a<b)?a:b;
}

inline double min(double a, double b, double c)
{
	return min(min(a,b),c);
}

inline double d(punct a, punct b)
{
	return sqrt((double)(a.x - b.x) * (a.x - b.x) + (double)(a.y - b.y) * (a.y - b.y));
}

void citire()
{
	scanf("%i",&n);
	for (int i = 1; i <= n; ++i)
		scanf("%i%i",&a[i].x,&a[i].y);
}

bool sortare_dupa_abscisa(punct i, punct j)
{
	if (i.x <= j.x)
		return true;
	return false;
}

bool sortare_dupa_ordonata(punct i, punct j)
{	
	if (i.y <= j.y)
		return true;
	return false;
}

void construieste_Y(double S,int X, int i, int j)
{
	nY = 0;
	for (int k = i; k <= j; ++k)
		if ((X-S <= o[k].x)&&(o[k].x <= X+S))
			Y[++nY] = o[k];
}

double dist(int i, int j)
{
	double S;
	if (j - i + 1 == 2)//2 numere
		return d(a[i],a[i+1]);
	if (j - i + 1 == 3)//3 numere
		return min(d(a[i],a[i+1]),d(a[i+1],a[i+2]),d(a[i],a[i+2]));
	//Divide et impera
	int impart = (i+j)/2;//intervalul [i,impart] apartine primei jumatati, [impart+1,j] celei de-a doua.
	S = min(dist(i,impart),dist(impart+1,j));
	construieste_Y(S,a[impart].x, i, j);
	double S_prim = d(Y[1],Y[2]);//initializare
	for (int p = 1; p <= nY-1; ++p)
		for (int q = p+1; q <= nY && q <= p + 7; ++q)
			S_prim = min(d(Y[p],Y[q]),S_prim);
	return min(S,S_prim);
}

int main()
{
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
	citire();
	int cn = n;
	sort (a+1,a+n+1,sortare_dupa_abscisa);
	memcpy(o+1,a+1,2*n*sizeof(a[0]));//se detoneaza n fara motiv la numere mari
	sort (o+1,o+n+1,sortare_dupa_ordonata);
	n = cn;
	printf("%lf",dist(1,n));
	return 0;
}