Cod sursa(job #2072703)

Utilizator andreiDumysTrofin Andrei andreiDumys Data 22 noiembrie 2017 08:36:26
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.61 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;
	}
};*/



double Distanta(pair<int,int> A, pair<int,int> B)
{
	return sqrt((B.first - A.first) * (B.first - A.first) + (B.second - A.second) * (B.second - A.second));
}




pair<pair<pair<int,int>, pair<int,int>>, double> ClosestPoints(vector<pair<int,int>> Px, vector<pair<int,int>> Py,int left,int right)
{


    if (left >= right - 1)
        return make_pair(make_pair(Px[0], Px[0]), 2147483647);
    else
    if (right - left == 2)
    {
        if (Py[left] > Py[left + 1])
            swap(Py[left], Py[left + 1]);
        return make_pair(make_pair(Px[left], Px[left+1]), Distanta(Px[left], Px[left + 1]));
    }




    int mid=(left+right)/2;
	pair<int,int> midPoint = Px[mid];

	auto d1 = ClosestPoints(Px, Py,left,mid);
	auto d2 = ClosestPoints(Px, Py,mid,right);

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

	vector<pair<int,int>> puncteDinRegiuneaLuiL;

    merge(Py.begin() + left, Py.begin() + mid, Py.begin() + mid,  Py.begin() + right, puncteDinRegiuneaLuiL.begin());  ///Interclasare
    copy(puncteDinRegiuneaLuiL.begin(), puncteDinRegiuneaLuiL.begin() + (right - left), Py.begin() + left);

	for (int i=left;i<right;i++)
		if (abs(Py[i].second - midPoint.first)<d.second)
			puncteDinRegiuneaLuiL.push_back(Py[i]);

	for (unsigned i = 0; i < puncteDinRegiuneaLuiL.size(); i++)
	{
		for (unsigned j = i + 1; j < puncteDinRegiuneaLuiL.size() && (puncteDinRegiuneaLuiL[j].second - puncteDinRegiuneaLuiL[i].second) < 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<pair<int,int>> vector_puncte_sortatX;
	vector<pair<int,int>> vector_puncte_sortatY;
	int n;
	double x, y;
	FILE >> n;
	while (FILE >> x >> y)
	{
		vector_puncte_sortatX.push_back(make_pair(x,y));
		vector_puncte_sortatY.push_back(make_pair(y,x));
	}

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


	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;
}