Cod sursa(job #2082817)

Utilizator SurrealEverythingDumitrescu Gabriel Horia SurrealEverything Data 6 decembrie 2017 20:01:29
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 3.44 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<float.h>
#include<cmath>
#include <iomanip>
using namespace std;
struct point
{
	int x, y;
};
vector<point> xOrderedPoints, yOrderedPoints;
bool abscissaCompare(point a, point b) 
{
	if(a.x!=b.x)
		return a.x < b.x;
	else
		return a.y < b.y;
}
bool ordinateCompare(point a, point b)
{
	if (a.y != b.y)
		return a.y < b.y;
	else
		return a.x < b.x;
}
bool ordinateSmallerOrEqual(point a, point b)
{
	return a.y <= b.y;
}
double computeDistance(point a, point b)
{
	return sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));
}
void read()
{
	ifstream in("cmap.in");
	int n;
	point temp;
	in >> n;
	for (int i = 0; i < n; ++i)
	{
		in >> temp.x >> temp.y;
		xOrderedPoints.push_back(temp);
	}
	sort(xOrderedPoints.begin(), xOrderedPoints.end(), abscissaCompare);
	yOrderedPoints = xOrderedPoints;
}
/*
void merge(vector<point> &points, int left, int middle, int right)
{
	vector<point> aux;
	aux.resize(right - left + 1);
	merge(points.begin() + left, points.begin() + middle, points.begin() + middle+1, points.begin() + right, aux.begin(), ordinateCompare);
	copy(aux.begin(), aux.end(), points.begin() + left);
}
*/
void merge(vector<point> &points, int left, int middle, int right)
{
	vector<point> leftPoints(points.begin()+left, points.begin() + middle+1);
	vector<point> rightPoints(points.begin()+middle+1, points.begin()+right+1);
	vector<point>::iterator i=leftPoints.begin(), j=rightPoints.begin(), k=points.begin()+left;
	while (i != leftPoints.end() && j != rightPoints.end())
	{
		if (ordinateSmallerOrEqual(*i, *j))
		{
			*k = *i;
			++i;
		}
		else
		{
			*k = *j;
			++j;
		}
		++k;
	}
	while(i!= leftPoints.end())
	{
		*k = *i;
		++i;
		++k;
	}
	while (j != rightPoints.end())
	{
		*k = *j;
		++j;
		++k;
	}
}
double divideEtImpera(int left, int right)
{
	double minDistance = DBL_MAX;
	if (right-left+1 < 4)
	{
		double tempDistance;
		sort(yOrderedPoints.begin()+left, yOrderedPoints.begin()+right+1, ordinateCompare);
		for(vector<point>::iterator i=xOrderedPoints.begin() + left; i!=xOrderedPoints.begin() + right; ++i)
			for (vector<point>::iterator j = i+1; j != xOrderedPoints.begin() + right +1 ; ++j)
			{
				tempDistance = computeDistance(*i, *j);
				minDistance = min(minDistance, tempDistance);
			}
	}
	else
	{
		double leftMinDistance, rightMinDistance;
		int middle = (left + right) / 2;
		leftMinDistance = divideEtImpera(left, middle);
		rightMinDistance = divideEtImpera(middle + 1, right);
		minDistance = min(leftMinDistance, rightMinDistance);
		merge(yOrderedPoints, left, middle, right);
		vector<point> yBand;
		for (vector<point>::iterator i = yOrderedPoints.begin() + left; i != yOrderedPoints.begin() + right + 1; ++i)
		{
			if(i->x != xOrderedPoints[middle].x || i->y != xOrderedPoints[middle].y)
				if (abs(i->x - xOrderedPoints[middle].x) <= minDistance)
					yBand.push_back(*i);
		}
		for (vector<point>::iterator i = yBand.begin(); i != yBand.end() - 1; ++i)
		{
			int count = 0;
			for (vector<point>::iterator j =i+1; count < 7 && j!=yBand.end(); ++j, ++count)
			{
				minDistance = min(minDistance, computeDistance(*i, *j));
			}
			count = 0;
		}
	}
	return minDistance;
}
void print(double distance)
{
	ofstream out("cmap.out");
	out << fixed << setprecision(6) << distance;
}
int main()
{
	read();
	print(divideEtImpera(0, xOrderedPoints.size()-1));
	return 0;
}