Cod sursa(job #2496463)

Utilizator justicebringerArghire Gabriel justicebringer Data 20 noiembrie 2019 21:45:21
Problema Cele mai apropiate puncte din plan Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

typedef pair <double, double> point;	//punct 2D
const int MAXN = 100010;	//constanta
const double INF = 1e16;	//constanta
const int PRECISION = 6;	//pentru afisare cu 6 zecimale
vector <point> Vy(MAXN);
vector <point> V(MAXN);
vector <point> final_interclasare(MAXN);
int N;

//functie pentru distanta dintre 2 puncte
double dist(point p1, point p2) {
	return sqrt((p1.first - p2.first) * (p1.first - p2.first) +
		(p1.second - p2.second) * (p1.second - p2.second));
}

//functie pentru compararea bruta a maxim 3 puncte
double bruteForce(int from, int to) {
	double minDist = INF;

	for (int i = from; i <= to; i++)
		for (int j = i + 1; j <= to; j++)
			minDist = min(minDist, dist(V[i], V[j]));

	return minDist;
}

//sortare bruteForce
void sort_BruteForce(int left, int right) {
	for (int i = left; i <= right; i++)
		for (int j = i + 1; j <= right; j++)
			if (Vy[i] > Vy[j])
				swap(Vy[i], Vy[j]);
}

//functie unde aflam rezultatul final
double closestOverlapping(vector <point>& strip, double minDist) {
	//aici aflam distanta minima dintre cele maxim 8 puncte din vectorul strip
	for (int i = 0; i < strip.size(); i++) {
		for (int j = i + 1; j < strip.size() && (strip[j].second - strip[i].second) < minDist; j++)
			if(strip[i].first != 0 && strip[j].first != 0)
				minDist = min(minDist, dist(strip[i], strip[j]));
	}

	//returnare rezultat
	return minDist;
}

//dupa ce am sortat dupa y avem nevoie sa interclasam partea din stanga cu partea din dreapta
void interclasare(int mid_index, int right_index) {
	final_interclasare.resize(right_index + 1);
	int i = 0, j = mid_index + 1;
	int k = 0;

	while (i <= mid_index && j <= right_index) {
		if (Vy[i] < Vy[j]) {
			final_interclasare[k++] = Vy[i];
			i++;
		}
		else {
			final_interclasare[k++] = Vy[j];
			j++;
		}
	}

	while (i <= mid_index) {
		final_interclasare[k++] = Vy[i];
		i++;
	}

	while (j <= right_index) {
		final_interclasare[k++] = Vy[j];
		j++;
	}
}

//functie in urma careia aflam cele maxim 8 puncte de comparat
double minDist(int left, int right) {
	if (right - left + 1 <= 3) {	//daca avem doar 3 elemente le comparam cu bruteForce
		for (int i = left; i <= right; i++)
			Vy[i] = V[i];
		sort_BruteForce(left, right);

		return bruteForce(left, right);
	}

	int mid = left + (right - left) / 2;
	point midPoint = V[mid];

	double leftDist = minDist(left, mid);	//punctele din stanga
	double rightDist = minDist(mid + 1, right);	//punctele din dreapta
	double localMinDist = min(leftDist, rightDist);	//distanta cea mai mica

	//interclasare cu i de la left si j de la mid + 1
	interclasare(mid, right);

	return min(localMinDist, closestOverlapping(final_interclasare, localMinDist)); //aici comparam cele maxim 8 puncte din solutia finala
}

int main()
{
	ifstream fin("cmap.in");
	fin >> N;

	for (int i = 0; i < N; i++) {	//citire din fisier
		point p;

		fin >> p.first;
		fin >> p.second;
		
		V[i] = p;
	}

	//resize la N
	V.resize(N);	
	Vy.resize(N);

	sort(V.begin(), V.end());		//sortare dupa coordonata x

	ofstream fout("cmap.out");	//afisare in fisier
	fout << fixed << setprecision(PRECISION) << minDist(0, N - 1);

	fin.close();
	fout.close();
}