Cod sursa(job #721251)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 23 martie 2012 14:52:52
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.22 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;
int n;
typedef long long LL;
LL sol,infinit=1000000000000000001LL;
vector < pair<LL,LL> > X,Y,Z(100100);
pair<LL,LL> v[100100];

inline void Citire()
{
	int i,x,y,ns,poz;
	char s[30];
	ifstream fin("cmap.in");
	fin>>n;
	fin.getline(s,30);
	X.resize(n);
	Y.resize(n);
	for(i=0;i<n;i++)
	{
		fin.getline(s,30);
		ns=strlen(s);
		poz=0;
		x=0;
		while(s[poz]!=' ')
		{
			x=x*10+s[poz]-'0';
			poz++;
		}
		poz++;
		y=0;
		while(poz<ns)
		{
			y=y*10+s[poz]-'0';
			poz++;
		}
		X[i].first=(long long)x;
		X[i].second=(long long)y;
	}
	fin.close();
}

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

inline LL Divide_et_Impera(int st,int dr,vector < pair<LL,LL> > &X,vector < pair<LL,LL> > &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;
	LL 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()
{
	int i;
	sort(X.begin(),X.end());
	for(i=0;i<n;i++)
		Y[i]=make_pair(X[i].second,X[i].first);
	sol=Divide_et_Impera(0,n,X,Y);
}

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

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