Cod sursa(job #930980)

Utilizator taigi100Cazacu Robert taigi100 Data 27 martie 2013 22:11:54
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<stdio.h>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
#define w(a) vector< pair<long long,long long> >& a
#define itr vector < pair<long long,long long> >::iterator 
#define max 100005
#define inf 0x3f3f3f3f
typedef long long i64;
vector< pair<long long,long long> > v(max),x,y;
int n;


long long dist( pair<long long,long long>& a, pair<long long,long long>& b )
{
	return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
long long mind(int left,int right,w(x),w(y))
{
	if(left>=right-1)
		return inf;
	else if(right-left==2)
	{
		if(y[left]>y[left+1])
			swap(y[left],y[left+1]);
		return dist(x[left],x[left+1]);
	}

	int mid=(left+right)/2;
	i64 best=min(mind(left,mid,x,y),mind(mid,right,x,y));

	merge(y.begin()+left,y.begin()+mid,y.begin()+mid,y.begin()+right,v.begin());
	copy(v.begin(),v.begin() + (right-left),y.begin() +left);

	int sz=0;
	for(int i=left; i<right ;i++)
		if((abs(y[i].second-x[mid].first))<=best)
			v[sz++]=y[i];
	for(int i=0;i<sz-1;i++)
		for(int j=i+1;j<sz && j-i<8 ; ++j)
			best=min(best,dist(v[i],v[j]));
	return best;
}

int main()
{
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);

	scanf("%d",&n);
	x.resize(n),y.resize(n);
	for(int i=0;i< (int) x.size();i++)
		scanf("%d%d",&x[i].first,&x[i].second);

	sort(x.begin(),x.end());
	for(int i=0;i<(int) y.size();i++)
		y[i]= make_pair(x[i].second,x[i].first);

	printf("%.6f",sqrt((long double)mind(0,(int) x.size(),x,y)));
}