Cod sursa(job #982055)

Utilizator Anca_PaneaPanea Anca Anca_Panea Data 8 august 2013 13:33:09
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
using namespace std;
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<climits>
#include<algorithm>
# define Nmax 100005
pair <int,int> P[Nmax],V[Nmax];
int N,k;
void Read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		P[i]=make_pair(x,y);
	}
}
inline long long dist(pair <int,int> a,pair <int,int> b)
{
	return 1LL*(a.first-b.first)*(a.first-b.first)+1LL*(a.second-b.second)*(a.second-b.second);
}
long long Solve()
{
	long long Min=LLONG_MAX;
	for(int i=1;i<N;i++)
		for(int j=i+1;j<=N;j++)
		{
			Min=min(Min,dist(P[i],P[j]));
		}
	return Min;
}

long long DEI(int st, int dr)
{
	if(st==dr)
		return LLONG_MAX;
	if(dr-st==1)
		return dist(P[st],P[dr]);
	int mid=(st+dr)/2;
	long long a=DEI(st,mid);
	long long b=DEI(mid+1,dr);
	long long Minim=min(a,b);
	k=0;
	for(int i=st;i<=dr;i++)
		if(abs(P[i].first-P[mid].first)<Minim)
			{
			V[++k]=P[i];
			}
	long long Min=LLONG_MAX;
	for(int i=1;i<k;i++)
		for(int j=i+1;j<=k;j++)
		{
			Min=min(Min,dist(V[i],V[j]));
		}
	return Min;
}

int main()
{
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
	Read();
	sort(P+1,P+N+1);
	printf("%lf\n",sqrt((double)DEI(1,N)));
	return 0;
}