Cod sursa(job #405633)

Utilizator AndreyPAndrei Poenaru AndreyP Data 28 februarie 2010 14:27:55
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.6 kb
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<time.h>
#include<limits.h>
#include<algorithm>
#include<bitset>
using namespace std;
#define N 100010
#define fs first
#define sc second
#define mp make_pair
#define stg 0
#define dr 1
int n;
const double eps=1e-12;
pair<int,int> p[N],rez;
int x[N],y[N];
char cmp(double x,double y)
{
	if(x+eps<y)
		return -1;
	if(y+eps<x)
		return 1;
	return 0;
}
inline double dist(int x,int y)
{
	return sqrt((double)((p[x].fs-p[y].fs)*(p[x].fs-p[y].fs)+(p[x].sc-p[y].sc)*(p[x].sc-p[y].sc)));
}
bool comparx(const int &x,const int &y)
{
	if(p[x].fs<p[y].fs)
		return true;
	return false;
}
bool compary(const int &x,const int &y)
{
	if(p[x].sc<p[y].sc)
		return true;
	return false;
}
inline void citire()
{
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)
	{
		scanf("%d%d",&p[i].fs,&p[i].sc);
		x[i]=i;
		y[i]=i;
	}
	x[0]=n;
	y[0]=n;
	sort(x+1,x+n+1,comparx);
	sort(y+1,y+n+1,compary);
}
inline int modul(int x)
{
	if(x<0)
		return -x;
	return x;
}
pair<int,int> rezolva(int x[],int y[])
{
	if(x[0]<=3)
	{
		double d=3000000000.00,aux;
		pair<int,int> p1;
		for(int i=1; i<x[0]; ++i)
		{
			for(int j=i+1; j<=x[0]; ++j)
			{
				aux=dist(x[i],x[j]);
				if(aux<d)
				{
					d=aux;
					p1=mp(x[i],x[j]);
				}
			}
		}
		return p1;
	}
	int dim=x[0]/2+3;
	int *xs,*ys,*xd,*yd;
	xs=new int[dim];
	ys=new int[dim];
	xd=new int[dim];
	yd=new int[dim];
	bitset<N> unde;
	unde.reset();
	int aux=x[0]>>1;
	for(int i=1; i<=aux; ++i)
	{
		xs[i]=x[i];
		unde[x[i]]=stg;
	}
	xs[0]=aux;
	xd[0]=0;
	for(int i=aux+1; i<=x[0]; ++i)
	{
		xd[++xd[0]]=x[i];
		unde[x[i]]=dr;
	}
	ys[0]=yd[0]=0;
	for(int i=1; i<=y[0]; ++i)
	{
		if(unde[y[i]]==stg)
			ys[++ys[0]]=y[i];
		else
			yd[++yd[0]]=y[i];
	}
	pair<int,int> p1,p2,per;
	p1=rezolva(xs,ys);
	p2=rezolva(xd,yd);
	double d1=dist(p1.fs,p1.sc),d2=dist(p2.fs,p2.sc),dmin;
	if(cmp(d1,d2)!=1)
	{
		dmin=d1;
		per=p1;
	}
	else
	{
		dmin=d2;
		per=p2;
	}
	int dreapta=p[x[0]>>1].fs;
	int *y1;
	y1=new int[dim<<1];
	y1[0]=0;
	for(int i=1; i<=y[0]; ++i)
	{
		if(cmp((double)modul(p[y[i]].fs-dreapta),dmin)!=1)
			y1[++y1[0]]=y[i];
	}
	int j=min(8,y1[0]);
	for(int i=1; i<y1[0]; ++i)
	{
		for(int t=i+1; t<=j; ++t)
		{
			double aux1=dist(y1[i],y1[t]);
			if(cmp(aux1,dmin)==-1)
			{
				dmin=aux1;
				per=mp(y1[i],y1[t]);
			}
		}
		if(j<y1[0])
			++j;
	}
	return per;
}
int main()
{
	int start=clock();
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
	citire();
	rez=rezolva(x,y);
	printf("%lf\n",dist(rez.fs,rez.sc));
	//printf("%d %d ; %d %d\n",p[rez.fs].fs,p[rez.fs].sc,p[rez.sc].fs,p[rez.sc].sc);
	//printf("%lf\n",((double)clock()-start)/CLOCKS_PER_SEC);
	return 0;
}