Cod sursa(job #2072667)

Utilizator dark_knight2012Potec Tiberiu dark_knight2012 Data 22 noiembrie 2017 02:20:02
Problema Cele mai apropiate puncte din plan Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 3.56 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <float.h>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <limits.h>

using namespace std;

ifstream in("cmap.in");
ofstream out("cmap.out");


struct punct
{
	int x;
	int y;
};

int x1,y3,x2,y2;

int comparare_x(punct a, punct b)
{
	return a.x < b.x;
}

int comparare_y(punct a, punct b)
{
	return a.y < b.y;
}

double distanta_euclidiana(punct a, punct b)
{
	double x = a.x - b.x;
	double y = a.y - b.y;
	double distanta;
	distanta = pow(x, 2) + pow(y, 2);
	distanta =  sqrt(distanta);
	return distanta;
}

int citire(vector <punct> &vx, vector <punct> &vy)
{
	int n;
	in >> n;
	for (int i = 0; i < n; i++)
	{
		punct aux;
		in >> aux.x;
		in >> aux.y;
		vx.push_back(aux);
	}
	sort(vx.begin(), vx.end(), comparare_x);
	vy = vx;
	return 1;
}

int afisare(vector <punct> vx)
{
	for (auto it : vx)
	{
		out << it.x << " " << it.y << endl;
	}
	return 1;
}

double calculare_distanta_minima(vector <punct> &vx, int left, int right, vector <punct> &vy)
{
	if (right - left == 1) /// daca avem doar un punct la un anume moment
	{
		return INT_MAX;
	}
	if (right - left == 2) /// daca avem doua puncte la un anume moment
	{
		/*
		if (vy.at(left).y > vy.at(left + 1).y)
		{
			swap(vy.at(left), vy.at(left + 1));
		}
		*/
		return distanta_euclidiana(vx.at(0), vx.at(1));
	}

	int mij =  (left + right) / 2; /// impartim vectorul in 2

	double distanta_minima_stanga = calculare_distanta_minima(vx, left, mij, vy); /// calculam recursiv distanta minima din partea stanga a vectorului
	double distanta_minima_dreapta = calculare_distanta_minima(vx, mij, right, vy); /// calculam recursiv distanta minima din partea dreapta a vectorului
	double distanta_minima_temporara = min(distanta_minima_stanga, distanta_minima_dreapta); /// luam minimul distantelor dintre cele doua valori calculate anterior

	vector<punct> puncte_auxiliare(right - left);

	/*
	merge(vy.begin() + left, vy.begin() + mij, vy.begin() + mij, vy.begin() + right, puncte_auxiliare.begin(), comparare_y); ///interclaseaza dupa oy(ordonata) in puncte_auxiliare vectorii (vy + left -> vy+mij) & (vy+mij -> my+right)
	copy(puncte_auxiliare.begin(), puncte_auxiliare.begin() + (right - left), vy.begin() + left);
	*/

	vector <punct> aux;

	for (int i = left; i < right; i++) /// parcurgem elementele din vy
	{
		if (abs(vy.at(i).x - vx.at(mij).x) <= distanta_minima_temporara) /// in aux le bagam doar pe cele care au distanta de la coordonata x la mijloc (la mediana verticala) (de ambele parti(Abs)) mai mica ca distanta_minima_temporara
		{
			aux.push_back(vy.at(i));
		}
	}

	//sort(aux.begin(),aux.end(),comparare_y); /// sortare 

	double distanta_minima_finala = distanta_minima_temporara; /// presupunem ca distanta minima finala este egala cu cea temporara

	for (int i = 0; i < aux.size(); i++)
	{
		for (int j = i + 1; j < aux.size() && aux.at(j).y - aux.at(i).y <= distanta_minima_temporara; j++)
		{
			double distanta_auxiliara = distanta_euclidiana(aux.at(i), aux.at(j));
			if (distanta_auxiliara < distanta_minima_finala)
			{
				distanta_minima_finala = distanta_auxiliara;
				x1=aux.at(i).x;
				y3=aux.at(i).y;
				x2=aux.at(j).x;
				y2=aux.at(j).y;
			}
		}
	}
	return distanta_minima_finala;
}



int main()
{
	vector <punct> vx;
	vector <punct> vy;
	citire(vx, vy);
	//afisare(vy);
	out << fixed;
	out << setprecision(6) << calculare_distanta_minima(vx, 0, vx.size(), vy)<<endl;
	out<<x1<<" "<<y3<<endl<<x2<<" "<<y2;
	return 0;
}