Cod sursa(job #2071335)

Utilizator robert_fanrRobert Banu robert_fanr Data 20 noiembrie 2017 16:50:05
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

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

struct punct {
	int x=0;
	int y=0;
};

double distEuclid(punct a, punct b) {
	double x = a.x - b.x;
	double y = a.y - b.y;
	double dist;

	dist = pow(x, 2) + pow(y, 2);           //calculating distance by euclidean formula
	dist = sqrt(dist);                  //sqrt is function in math.h

	return dist;
}

double distMinPunctePlanRec(vector <punct> & puncte, int st, int dr, vector<punct> &puncteY) {
	if (dr-st == 1) {
		return INT_MAX;
	}
	if (dr-st == 2) {
		return distEuclid(puncte[0], puncte[1]);
	}

	int m = (st + dr) / 2;
	double distStanga = distMinPunctePlanRec(puncte, st, m, puncteY);
	double distDreapta = distMinPunctePlanRec(puncte, m, dr, puncteY);
	double distMinStDr = min(distStanga, distDreapta);

	//construim banda
	vector <punct> banda;
	for (int i = 0; i < puncteY.size(); ++i) {
		if (abs(puncteY[i].x - puncte[m].x) <= distMinStDr)
			banda.push_back(puncteY[i]);
	}
	//rezolvam banda
	double distMinOverall = distMinStDr;
	for (int i=0; i<banda.size(); ++i)
		for (int j = i + 1; j < banda.size() && banda[j].y - banda[i].y <= distMinStDr; ++j) {
			double distCur = distEuclid(banda[i], banda[j]);
			if (distCur < distMinOverall)
				distMinOverall = distCur;
		}

	return distMinOverall;
}

bool cmpDupaX(const punct& a, const punct& b)
{
	return a.x < b.x;
}

bool cmpDupaY(const punct& a, const punct& b)
{
	return a.y < b.y;
}


void distMinPunctePlan() {
	int n;
	in >> n;

	vector <punct> puncte(n);
	for (int i = 0; i < n; ++i) {
		in >> puncte[i].x;
		in >> puncte[i].y;
	}

	sort(puncte.begin(), puncte.end(), cmpDupaX);

	vector <punct> puncteY = puncte;

	sort(puncteY.begin(), puncteY.end(), cmpDupaY);

	out << fixed;
	out << setprecision(6) << distMinPunctePlanRec(puncte, 0, puncte.size(), puncteY) << "\n";
}

int main()
{
	distMinPunctePlan();
	return 0;
}