Cod sursa(job #610320)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 26 august 2011 17:01:08
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <limits>
#include <cmath>

using namespace std;

struct Point
{
	Point()
	{}
	Point(const int xx, const int yy) : x(xx), y(yy)
	{}
	
	double 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 true;
	}
};

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;
	double crtDist = numeric_limits<int>::max();
	multiset<Point, VComp> candidates;
	
	//cout << "Start rocessing\n";
	
	for (vector<Point>::iterator it=vPoints.begin(); it!=vPoints.end(); ++it)
	{
		while (it->x - vPoints[leftMostCandidateIndex].x > crtDist)
		{
			candidates.erase(vPoints[leftMostCandidateIndex]);
			leftMostCandidateIndex++;
		}
		
		for (multiset<Point, VComp>::iterator itm=candidates.begin(); itm!=candidates.end(); ++itm)
		{
			double dist = sqrt((it->x - itm->x)*(it->x - itm->x) + (it->y - itm->y)*(it->y - itm->y));
			//cout << "Intermediate dist = " << dist << endl;
			
			if (dist < crtDist)
			{
				crtDist = dist;
			}
		}
		
		candidates.insert(*it);
	}
	
	//cout.precision(40);
	//cout << (double)sqrt(crtDist) << endl;
	return 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(40);
	fout << ClosestPair(vPoints) << endl;
	
	fin.close();
	fout.close();
	return 0;
}