Cod sursa(job #579356)

Utilizator ChallengeMurtaza Alexandru Challenge Data 12 aprilie 2011 08:42:11
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;

const char InFile[]="cmap.in";
const char OutFile[]="cmap.out";
const long long LLINF=1LL<<62;
const int MaxN=100111;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s_point
{
	s_point(long long _x=0, long long _y=0):x(_x),y(_y){}
	long long x,y;
};

struct cmp
{
	inline bool operator() (const s_point &a, const s_point &b)
	{
		return a.x<b.x;
	}
};

int N,indF;
s_point P[MaxN],F[MaxN];

inline long long dist(const s_point &a, const s_point &b)
{
	long long dx=a.x-b.x;
	long long dy=a.y-b.y;
	return dx*dx+dy*dy;
}

inline void merge(int st, int dr)
{
	int m=st+((dr-st)>>1);
	s_point T[MaxN];
	int ind1=st;
	int ind2=m+1;
	int tind=st-1;
	while(ind1<=m && ind2<=dr)
	{
		if(P[ind1].y<P[ind2].y)
		{
			T[++tind]=P[ind1];
			++ind1;
		}
		else
		{
			T[++tind]=P[ind2];
			++ind2;
		}
	}
	while(ind1<=m)
	{
		T[++tind]=P[ind1];
		++ind1;
	}
	while(ind2<=dr)
	{
		T[++tind]=P[ind2];
		++ind2;
	}
	for(register int i=st;i<=dr;++i)
	{
		P[i]=T[i];
	}
}

long long cmap(int st, int dr)
{
	if(st>=dr)
	{
		return LLINF;
	}
	if(dr==st+1)
	{
		if(P[st].y>P[dr].y)
		{
			swap(P[st],P[dr]);
		}
		return dist(P[st],P[dr]);
	}
	int m=st+((dr-st)>>1);
	int d=P[m].x;
	long long s=min(cmap(st,m),cmap(m+1,dr));
	merge(st,dr);
	indF=0;
	for(int i=st;i<=dr;++i)
	{
		if(abs(P[i].y-d)<=s)
		{
			F[++indF]=P[i];
		}
	}
	for(int i=1;i<=indF;++i)
	{
		for(int j=1;j<=7;++j)
		{
			if(i+j>indF)
			{
				break;
			}
			s=min(s,dist(F[i],F[i+j]));
		}
	}
	return s;
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>P[i].x>>P[i].y;
	}
	fin.close();
	
	sort(P+1,P+1+N,cmp());
	
	fout<<setprecision(50)<<fixed<<sqrt((double)(cmap(1,N)));
	fout.close();
	return 0;
}