Cod sursa(job #2072621)

Utilizator andreiDumysTrofin Andrei andreiDumys Data 21 noiembrie 2017 23:36:59
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.3 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iomanip>

using namespace std;

struct Punct2D
{
	double x;
	double y;

	Punct2D(double xx,double yy)
	{
		x = xx;
		y = yy;
	}
};

bool SorteazaDupaX(const Punct2D& A, const Punct2D& B)
{
	if (A.x > B.x)
		return false;

		if (A.x == B.x)
		{if (A.y > B.y)
				return false;
			else
				return true;
	}
	return true;
}

bool SorteazaDupaY(const Punct2D& A, const Punct2D& B)
{
	if (A.y > B.y)
		return false;

	if (A.y == B.y)
	{
		if (A.x > B.x)
			return false;
		else
			return true;
	}

	return true;
}

double Distanta(Punct2D A, Punct2D B)
{
	return sqrt((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y));
}

bool operator<(Punct2D A, Punct2D B)
{
	if (A.y >= B.y)
		return true;
	else
		return false;
}


pair<pair<Punct2D,Punct2D>, double> ClosestPoints(vector<Punct2D> Px, vector<Punct2D> Py,int begin,int end)
{

	if (Px.size() <= 3)
	{
		pair<pair<Punct2D, Punct2D>,double> min= make_pair(make_pair(Px[0], Px[0]), 2147483647);
		if (Px.size() == 1)
			return min;

		for (unsigned i=0;i<Px.size();i++)
			for (unsigned j = i+1; j<Px.size(); j++)
				if (Distanta(Px[i], Px[j]) < min.second)
					min = make_pair(make_pair(Px[i], Px[j]), Distanta(Px[i], Px[j]));
		return min;

	}

	int mid = Px.size() / 2;
	Punct2D midPoint = Px[mid];
	//Impartim planul in 2 subplanuri
	vector<Punct2D> Ax(Px.begin(), Px.begin() + Px.size() / 2);
	vector<Punct2D> Bx(Px.begin() + Px.size() / 2, Px.end());
	vector<Punct2D> Ay;
	vector<Punct2D> By;

	for (auto p:Py)
	{
		if (p.x <= midPoint.x)
			Ay.push_back(p);
		else
			By.push_back(p);
	}

	auto d1 = ClosestPoints(Ax,Ay,begin,mid);
	auto d2 = ClosestPoints(Bx, By,mid+1,end);

	auto d = d1.second < d2.second ? d1 : d2; //Minimul dintre cele 2 distante;



	vector<Punct2D> puncteDinRegiuneaLuiL;

	merge(Py.begin() + begin, Py.begin() + mid, Py.begin() + mid, Py.begin() + end, puncteDinRegiuneaLuiL.begin());
	copy(puncteDinRegiuneaLuiL.begin(), puncteDinRegiuneaLuiL.begin() + (end - begin), Py.begin() + begin);

	for (auto p : Py)
		if (abs(p.x-midPoint.x)<d.second)
			puncteDinRegiuneaLuiL.push_back(p);

	for (unsigned i = 0; i < puncteDinRegiuneaLuiL.size(); i++)
	{
		for (unsigned j = i + 1; j < puncteDinRegiuneaLuiL.size() && (puncteDinRegiuneaLuiL[j].y - puncteDinRegiuneaLuiL[i].y) < d.second; j++)
			d = Distanta(puncteDinRegiuneaLuiL[i], puncteDinRegiuneaLuiL[j]) < d.second ? make_pair(make_pair(puncteDinRegiuneaLuiL[i], puncteDinRegiuneaLuiL[j]), Distanta(puncteDinRegiuneaLuiL[i], puncteDinRegiuneaLuiL[j])) : d;
	}
	return  d;
}



int main()
{

	ifstream FILE("cmap.in");
	ofstream FILEO("cmap.out");
	vector<Punct2D> vector_puncte_sortatX;
	vector<Punct2D> vector_puncte_sortatY;
	int n;
	double x, y;
	FILE>>n;
	while (FILE >> x >> y)
	{
		vector_puncte_sortatX.push_back(Punct2D(x, y));
		vector_puncte_sortatY.push_back(Punct2D(x, y));
	}

	 sort(vector_puncte_sortatX.begin(), vector_puncte_sortatX.end(), SorteazaDupaX);


	auto rezultat = ClosestPoints(vector_puncte_sortatX, vector_puncte_sortatY,0,vector_puncte_sortatX.size()-1);

	FILEO<<fixed<<setprecision(6)<<rezultat.second;

    FILE.close();
    FILEO.close();


	return 0;
}