Cod sursa(job #2495533)

Utilizator TiberiuDTiberiu Danciu TiberiuD Data 19 noiembrie 2019 16:36:41
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.71 kb
/*
Sample input:
10
26 77
12 37
14 18
19 96
71 95
91 9
98 43
66 77
2 75
94 91
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdint>


using namespace std;

struct Punct {
	int x, y;
};

bool ComparaAbscise(Punct A, Punct B) {
	return A.x < B.x;
}

bool ComparaOrdonate(Punct A, Punct B) {
	return A.y < B.y;
}

inline int distantaPatrata(Punct A, Punct B) {
	return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

inline float distanta(Punct A, Punct B) {
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

float cmap(int pozStart, int pozSfarsit, const vector<Punct> &Puncte) {
	if (pozSfarsit - pozStart <= 3) {
		float distMin = INT32_MAX;
		for (int i = pozStart; i <= pozSfarsit - 1; i++)
			for (int j = i + 1; j <= pozSfarsit; j++)
				distMin = min(distMin, distanta(Puncte[i], Puncte[j]));
		return distMin;
	}

	int dreapta = (pozSfarsit + pozStart) / 2;

	float minimStanga = cmap(pozStart, dreapta, Puncte);
	float minimDreapta = cmap(dreapta + 1, pozSfarsit, Puncte);
	float minimGlobal = min(minimStanga, minimDreapta);


	// Merge

	vector<Punct> PuncteApropiate;
	PuncteApropiate.push_back(Puncte[dreapta]);

	int currentX = Puncte[dreapta].x;

	// Stanga
	for (int poz = dreapta - 1, delta = currentX - Puncte[dreapta - 1].x; delta <= minimGlobal && poz >= 0; poz--) {
		PuncteApropiate.push_back(Puncte[poz]);
		delta = currentX - Puncte[poz].x;
	}

	// Dreapta
	for (int poz = dreapta + 1, delta = Puncte[dreapta + 1].x - currentX; delta <= minimGlobal && poz < Puncte.size(); poz++) {
		PuncteApropiate.push_back(Puncte[poz]);
		delta = Puncte[poz].x - currentX;
	}

	// Aici ar trebui facuta interclasare
	sort(PuncteApropiate.begin(), PuncteApropiate.end(), ComparaOrdonate);

	// Determinare minim intre submultimi
	int distMin = INT32_MAX;
	int distPozVerificari = min(7, (int)PuncteApropiate.size() - 1);
	for (int i = 0; i < PuncteApropiate.size() - distPozVerificari; i++)
		for (int j = i + 1; j <= i + distPozVerificari && j < PuncteApropiate.size(); j++)
			distMin = min(distMin, distantaPatrata(PuncteApropiate[i], PuncteApropiate[j]));

	return min(minimGlobal, sqrtf(distMin));
}

int problema_4(ifstream &in, ofstream &out) {
	vector<Punct> Puncte;
	int n;

	in >> n;
	Puncte.resize(n);

	for (auto &Punct : Puncte)
		in >> Punct.x >> Punct.y;

	sort(Puncte.begin(), Puncte.end(), ComparaAbscise);

	out << cmap(0, Puncte.size() - 1, Puncte);

	return 0;
}


int main() {
	ifstream in("date.in");
	ofstream out("date.out");

	if (!in || !out)
		return 1;

	problema_4(in, out);

	in.close();
	out.close();

	return 0;
}