Cod sursa(job #610366)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 26 august 2011 19:09:36
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <limits>
#include <cmath>

using namespace std;

typedef long long int64;

struct Point
{
	Point()
	{}
	Point(const int xx, const int yy) : x(xx), y(yy)
	{}
	
	int x,y;
};

struct VComp
{
	inline const bool operator() (const Point& p1, const Point& p2) const
	{
		if (p1.y < p2.y)
			return true;
		else if (p1.y > p2.y)
			return false;
		
		if (p1.x < p2.x)
			return true;
		if (p1.x > p2.x)
			return false;
		
		return false;
	}
};

struct HComp
{
	inline const bool operator() (const Point& p1, const Point& p2) const
	{
		if (p1.x < p2.x)
			return true;
		if (p1.x > p2.x)
			return false;

		if (p1.y < p2.y)
			return true;
		else if (p1.y > p2.y)
			return false;
		
		return true;
	}
};

double ClosestPair(vector<Point>& vPoints)
{
	int leftMostCandidateIndex=0;
	int64 crtDist = numeric_limits<int64>::max();
	multiset<Point, VComp> candidates;
	
	for (vector<Point>::iterator it=vPoints.begin(); it!=vPoints.end(); ++it)
	{
		while (abs(it->x - vPoints[leftMostCandidateIndex].x) > sqrt(crtDist))
		{
			candidates.erase(vPoints[leftMostCandidateIndex]);
			leftMostCandidateIndex++;
		}
		
		for (multiset<Point, VComp>::iterator itm=candidates.begin(); itm!=candidates.end(); ++itm)
		{
			int64 dist = (int64)(it->x - itm->x)*(it->x - itm->x) + (int64)(it->y - itm->y)*(it->y - itm->y);
			
			if (dist < crtDist)
			{
				crtDist = dist;
			}
		}
		
		candidates.insert(*it);
		
	}

	return sqrt(crtDist);
}

int main()
{
	int n;
	vector<Point> vPoints;
	HComp hcomp;
	fstream fin("cmap.in", fstream::in);
	fstream fout("cmap.out", fstream::out);
	
	fin >> n;
	
	for (int i=0; i<n; ++i)
	{
		int x, y;
		fin >> x >> y;
		
		vPoints.push_back(Point(x,y));
	}

	sort(vPoints.begin(), vPoints.end(), hcomp);
	
	fout.precision(17);
	fout << ClosestPair(vPoints) << endl;
	
	fin.close();
	fout.close();
	return 0;
}