Cod sursa(job #610359)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 26 august 2011 18:47:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.64 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;
	
	//cout << "Start rocessing\n";
	
	for (vector<Point>::iterator it=vPoints.begin(); it!=vPoints.end(); ++it)
	{
		//cout << (it->x - vPoints[leftMostCandidateIndex].x) << " " << sqrt(crtDist) << endl;
		while (abs(it->x - vPoints[leftMostCandidateIndex].x) > sqrt(crtDist))
		{
			candidates.erase(vPoints[leftMostCandidateIndex]);
			leftMostCandidateIndex++;
			//cout << "Erased " << candidates.size() << endl;
		}
		//cout << "Done\n";
		
		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);
			//cout << "Intermediate dist = " << dist << endl;
			
			if (dist < crtDist)
			{
				crtDist = dist;
			}
		}
		
		candidates.insert(*it);
		/*cout << candidates.size() << endl;
		if (candidates.find(*it) == candidates.end())
		{
			cout <<"Crap\n";
			exit(0);
		}*/
		
	}
	
	//cout.precision(40);
	//cout << (double)sqrt(crtDist) << endl;
	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;
	//cout << n << endl;
	
	for (int i=0; i<n; ++i)
	{
		int x, y;
		fin >> x >> y;
		
		vPoints.push_back(Point(x,y));
		
		//cout << vPoints[i].x << " " << vPoints[i].y << endl;
	}

	//cout << endl;

	sort(vPoints.begin(), vPoints.end(), hcomp);
	/*for (int i=0; i<n; ++i)
	{
		cout << vPoints[i].x << " " << vPoints[i].y << endl;
	}*/
	
	fout.precision(17);
	fout << ClosestPair(vPoints) << endl;
	
	fin.close();
	fout.close();
	return 0;
}