Cod sursa(job #721290)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 23 martie 2012 15:39:25
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;
int n;
double sol,infinit=100000000000000001.0;
vector < pair<double,double> > X,Y,Z(100100);
pair<double,double> v[100100];

inline void Citire()
{
	int i;
	freopen("cmap.in","r",stdin);
	scanf("%d",&n);
	X.resize(n);
	Y.resize(n);
	for(i=0;i<n;i++)
	{
		scanf("%lf %lf",&X[i].first,&X[i].second);
		Y[i]=make_pair(X[i].second,X[i].first);
	}
}

inline double Dist(pair<double,double> A,pair<double,double> B)
{
	return sqrt((A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second));
}

inline double Divide_et_Impera(int st,int dr,vector < pair<double,double> > &X,vector < pair<double,double> > &Y)
{
	if(st>=dr-1)
		return infinit;
	
	// IMPERA
	if(dr-st==2)
	{
		if(Y[st]>Y[st+1])
			swap(Y[st],Y[st+1]);
		return Dist(X[st],X[st+1]);
	}
	
	// DIVIDE
	int mij=(st+dr)/2,lg,i,j,size;
	double distanta=min(Divide_et_Impera(st,mij,X,Y),Divide_et_Impera(mij,dr,X,Y));
	
	//	MERGE
	merge(Y.begin()+st,Y.begin()+mij,Y.begin()+mij,Y.begin()+dr,Z.begin());
	lg=dr-st;
	
	// COPY
	copy(Z.begin(),Z.begin()+lg,Y.begin()+st);
	
	// SELECTARE BANDA DE LATIME 2*distanta
	size=0;
	for(i=st;i<dr;i++)
	{
		//daca punctul se afla la distanta mai mica decat "distanta" de mijloc 
		//atunci intra in banda de latime 2*distanta
		if(abs(Y[i].second-X[mij].first)<=distanta)
			v[size++]=Y[i];
	}
	for(i=0;i<size-1;i++)
	{
		//in dreptunghiul format din 2 patrate de distanta*distanta
		//am maxim 8 puncte de luat in calcul,pe Z[i] si inca maxim 7
		for(j=i+1;j<size && j-i<8;j++) 
		{
			distanta=min(distanta,Dist(v[i],v[j]));
		}
	}
	return distanta;
}

inline void Rezolvare()
{
	sort(X.begin(),X.end());
	sol=Divide_et_Impera(0,n,X,Y);
}

inline void Afisare()
{
	freopen("cmap.out","w",stdout);
	printf("%.6lf\n",sol);
}

int main()
{
	Citire();
	Rezolvare();
	Afisare();
	return 0;
}