Cod sursa(job #700724)

Utilizator sefubanilorSefu Banilor sefubanilor Data 1 martie 2012 11:42:51
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <set>
#include <algorithm>

using namespace std;

const char InFile[]="cmap.in";
const char OutFile[]="cmap.out";
const int MaxN=100111;
const double DINF=1e64;

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

struct Point
{
	Point(int x=0, int y=0):x(x),y(y){}
	int x,y;
};

struct Point_cmp
{
	inline bool operator() (const Point &a, const Point &b)
	{
		if(a.x==b.x)
		{
			return a.y<b.y;
		}
		return a.x<b.x;
	}
};

struct Point_cmp2
{
	inline bool operator() (const Point &a, const Point &b)
	{
		if(a.y==b.y)
		{
			return a.x<b.x;
		}
		return a.y<b.y;
	}
};

inline double dist(const Point &A, const Point &B)
{
	double dx=(double)(A.x)-(double)(B.x);
	double dy=(double)(A.y)-(double)(B.y);
	return sqrt(dx*dx+dy*dy);
}

set<Point,Point_cmp2> H;

int N;
double sol;
Point P[MaxN];

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,Point_cmp());
	
	int st=1;
	sol=dist(P[1],P[2]);
	H.insert(P[1]);
	H.insert(P[2]);
	for(register int i=3;i<=N;++i)
	{
		int x=H.size();
		H.insert(P[i]);
		x=H.size();
		
		while(st<i && (double)(P[i].x-P[st].x)>sol)
		{
			H.erase(H.find(P[st]));
			x=H.size();
			++st;
		}
		
		x=H.size();
		
		set<Point,Point_cmp2>::iterator it=H.find(P[i]);
		set<Point,Point_cmp2>::iterator it2=it;
		if(it!=H.begin())
		{
			--it;
			for(register int j=1;j<=3;++j)
			{
				sol=min(sol,dist(*it,P[i]));
				if(it==H.begin())
				{
					break;
				}
				--it;
			}
		}
		++it2;
		for(register int j=1;j<=3;++j)
		{
			if(it2==H.end())
			{
				break;
			}
			sol=min(sol,dist(*it2,P[i]));
			++it2;
		}
	}
	
	fout<<fixed<<setprecision(20)<<sol;
	fout.close();
	return 0;
}