Cod sursa(job #1166975)

Utilizator dimitriepirghiePirghie Dimitrie dimitriepirghie Data 4 aprilie 2014 00:57:32
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
struct punct
{
	double x, y;
}puncte[100005],pctAux[100005];

bool SortAscX(punct a, punct b)
{
	if (a.x == b.x)
		return (a.y < b.y);
	return (a.x<b.x);
}
bool SortAscY(punct a, punct b)
{
	return (a.y < b.y);
}
double dist(punct a, punct b)
{
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double rezolva(int stg, int drep)
{
	//tratare caz elementar
	if (drep - stg + 1 <= 3)
	{
		double dmin = dist(puncte[stg], puncte[stg + 1]);
		for (int i = stg; i < drep; i++)
		{
			for (int j = i + 1; j <= drep; j++)
				dmin = min(dmin, dist(puncte[i], puncte[j]));
		}
		return dmin;
	}
	double solutieStg = rezolva(stg, (stg + drep) / 2);
	double solutieDrp = rezolva((stg + drep) / 2 + 1, drep);
	double DminCurent = min(solutieStg, solutieDrp);
	/////
	int mijloc = (stg + drep) / 2;
	double drepMij = (puncte[mijloc].x + puncte[mijloc+1].x) / 2;
	int nrPAux=0;
	for (int i = stg; i <= drep; i++)
	{
		if (abs(puncte[i].x - drepMij) <= DminCurent)
			pctAux[++nrPAux] = puncte[i];
	}
	/// sortam crescator dupa y;
	sort(pctAux + 1, pctAux + nrPAux + 1, SortAscY);
	int i, j;
	for (i = 1; i < nrPAux; i++)
	{
		for (j = i + 1; j<=min(nrPAux, i+7); j++)
		if (DminCurent > dist(pctAux[i], pctAux[j]))
			DminCurent = dist(pctAux[i], pctAux[j]);
	}
	return DminCurent;
}
int main()
{
	unsigned int n;
	ifstream inputStream("cmap.in");
	ofstream outputStream("cmap.out");
	inputStream >> n;
	for (int i = 1; i <= n; i++)
		inputStream >> puncte[i].x >> puncte[i].y;
	sort(puncte + 1, puncte + n + 1, SortAscX);
	outputStream <<setprecision(6)<<fixed<< rezolva(1, n);
	return 0;
}