Cod sursa(job #1024977)

Utilizator vladrochianVlad Rochian vladrochian Data 9 noiembrie 2013 13:06:33
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
struct point
{
	int x,y;
}p[100000];
int n;
int cmpx(point p1,point p2)
{
	return p1.x<p2.x;
}
int cmpy(point p1,point p2)
{
	return p1.y<p2.y;
}
double dist(point p1,point p2)
{
	double dx=p1.x-p2.x,dy=p1.y-p2.y;
	return sqrt(dx*dx+dy*dy);
}
double dmin(point *s,point *e)
{
	if(e-s==2)
		return dist(*s,*(s+1));
	if(e-s==3)
		return min(min(dist(*s,*(s+1)),dist(*(s+1),*(s+2))),dist(*s,*(s+2)));
	point *m=s+(e-s)/2,*pi;
	int drx=m->x;
	double dm=min(dmin(s,m),dmin(m,e));
	vector<point>area;
	vector<point>::iterator iti,itj;
	for(pi=m;(pi>=s)&&(drx-(pi->x)<=dm);pi--)
		area.push_back(*pi);
	for(pi=m+1;(pi<e)&&((pi->x)-drx<=dm);pi++)
		area.push_back(*pi);
	sort(area.begin(),area.end(),cmpy);
	for(iti=area.begin();iti<area.end()-1;iti++)
		for(itj=iti+1;(itj<area.end())&&(itj-iti<8);itj++)
			dm=min(dm,dist(*iti,*itj));
	return dm;
}
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int main()
{
	int i;
	fin>>n;
	for(i=0;i<n;i++)
		fin>>p[i].x>>p[i].y;
	sort(p,p+n,cmpx);
	fout<<setprecision(6)<<fixed<<dmin(p,p+n)<<"\n";
	return 0;
}