Cod sursa(job #2519606)

Utilizator DanielSim24Daniel Simionov DanielSim24 Data 7 ianuarie 2020 23:22:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.29 kb
// Problema 4 Varianta 3 Simionov Marius Daniel 242
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;

#define max 99999

struct point
{
	double x, y;
};

point puncte[max], aux[max], inter[max], a, b;

double distance(point a, point b)
{
	return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}

bool cmpX(point a, point b)
{
	return a.x < b.x;
}

bool cmpY(point a, point b)
{
	return a.y < b.y;
}

double dist_min(int left, int right)
{
	if (right - left + 1 == 3) //avem 3 puncte
	{
		sort(puncte + left, puncte + right, cmpY); 
		double d1 = distance(puncte[left], puncte[left + 1]);
		double d2 = distance(puncte[left + 1], puncte[left + 2]);
		double d3 = distance(puncte[left], puncte[left + 2]);
		double minim = d1;
		a = puncte[left];
		b = puncte[left + 1];
		if (d2 < minim) //aflam care sunt cele 2 puncte cele mai apropiate
		{
			minim = d2;
			a = puncte[left + 1];
			b = puncte[left + 2];
		}
		if (d3 < minim)
		{
			a = puncte[left];
			b = puncte[left + 2];
			minim = d3;
		}
		return minim;
	}
	if (right - left + 1 == 2) //avem doar 2 puncte
	{
		if (puncte[left].y > puncte[left + 1].y) //crescator
			swap(puncte[left], puncte[left + 1]);
		a = puncte[left];
		b = puncte[left + 1];
		return distance(puncte[left], puncte[left + 1]);
	}
	else // avem  mai mult de 3 puncte
	{
		int mijloc = (left + right) / 2; //impartim multimea de puncte a.i. sa avem n/2 puncte de fiecare parte
		double mediana = puncte[mijloc].x;
		double delta = min(dist_min(left, mijloc), dist_min(mijloc + 1, right));//apelam functia recursiv, pentru a imparti in subprobleme cat mai mici
		int nr = 0, i, j, k;

		//sortam prin interclasare(dupa valoarea ordonatei, y) punctele aflate de ambele parti ale medianei
		i = left;
		k = left;
		j = mijloc + 1;
		while (i <= mijloc && j <= right)
			if (puncte[i].y < puncte[j].y)
				aux[k++] = puncte[i++];
			else aux[k++] = puncte[j++];
		while (i <= mijloc)
			aux[k++] = puncte[i++];
		while (j <= right)
			aux[k++] = puncte[j++];

		for (i = left; i <= right; i++)
		{
			puncte[i] = aux[i];
			if (puncte[i].x - mediana <= delta && puncte[i].x - mediana >= -delta) // [-delta, delta]
				inter[++nr] = puncte[i]; //selectam doar punctele care se afla la o distanta de cel mult delta fata de mediana trasata
		}

		for (i = 1; i <= nr; i++)
		{
			int nr_vecini = min(nr, i + 7); //stim ca este suficient sa verificam cu urmatorii 7 vecini
			for (j = i + 1; j <= nr_vecini; j++)
				if (distance(inter[i], inter[j]) < delta) //verificam daca avem 2 puncte care sa ofere o noua distanta minima
				{
					delta = distance(inter[i], inter[j]);
					a = inter[i];
					b = inter[j];
				}
		}
		return delta;
	}
}

int main()
{
	ifstream fin("cmap.in");
	ofstream fout("cmap.out");
	int n, index;
	fin >> n;
	for (index = 1; index <= n; index++)
		fin >> puncte[index].x >> puncte[index].y;
	sort(puncte + 1, puncte + n + 1, cmpX);
	//fout << "Distanta minima este: "<<setprecision(6) << fixed << dist_min(0, n)<<"\n";
	//fout << "Punctele cele mai apropiate sunt de A( " << a.x << " , " << a.y << " ) si B( " << b.x << " , " << " ).";
	fout << setprecision(6) << fixed << dist_min(1, n);
	return 0;
}