Cod sursa(job #1047829)

Utilizator BuseSorinFMI Buse Sorin-Marian BuseSorin Data 4 decembrie 2013 22:05:04
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.39 kb
#include<iostream>
#include<fstream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;

struct punct{
	double x;
	double y;
};

long long distanta(punct x, punct y){

	return sqrt(pow(x.x - y.x, 2) + pow(x.y - y.y, 2));
}

int cmp(const void *x, const void *y){
	punct x1 = (*((punct*)x));
	punct y1 = (*((punct*)y));
	if (x1.x > y1.x){
		return 1;
	}
	else{
		if (x1.x == y1.x){
			if (x1.y > y1.y){
				return 1;
			}
			return -1;
		}
	}
	return -1;
}

punct puncte[100000];
vector<punct> Vpuncte;
bool sorteazaDupaY(const punct &a, const punct &b)
{
	return (a.y < b.y);
}

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

long long rezolva(int left, int right)
{
	long long d;
	if (right - left <= 2)
	{
		d = 10000000000000;

		for (int i = left; i < right; i++)
		{
			for (int j = i + 1; j <= right; j++)
			{
				d = min(distanta(puncte[i], puncte[j]), d);
			}
		}
		sort(puncte + left, puncte + right + 1, sorteazaDupaY);
		return d;
	}
	else
	{
		int middle = left + (right - left) / 2;

		d = min(rezolva(left, middle), rezolva(middle + 1, right));

		int l = left;
		int r = middle + 1;

		Vpuncte.clear();
		while ((l <= middle) && (r <= right))
		{
			if (sorteazaDupaY(puncte[l], puncte[r]) == true)
			{
				Vpuncte.push_back(puncte[l]);
				l++;
			}
			else
			{
				Vpuncte.push_back(puncte[r]);
				r++;
			}
		}

		while (l <= middle)
		{
			Vpuncte.push_back(puncte[l]);
			l++;
		}

		while (r <= right)
		{
			Vpuncte.push_back(puncte[r]);
			r++;
		}

		for (int i = left, k = 0; i <= right; i++, k++)
		{
			puncte[i] = Vpuncte[k];
		}

		for (int i = left; i <= right; i++)
		{
			for (int j = i + 1; (j <= right) && (j - i < 7); j++)
			{
				d = min(distanta(puncte[i], puncte[j]), d);
			}
		}

		return d;
	}
}

int main(){
	ifstream f("cmap.in");
	int n = 0; f >> n;
	
	for (int i = 0; i < n; i++){
		punct p;
		f >> p.x >> p.y;
		puncte[i] = p;
	}
	sort(puncte, puncte + n, sorteazaDupaX);
	/*double min = pow(10, 9);
	for (int i = 0; i < n-1; i++){
		for (int j = i + 1; j < n; j++){
			double dist = distanta(puncte[i], puncte[j]);
			if ( dist< min){
				min = dist;
				break;
			}
		}
	}*/
	ofstream o("cmap.out");
	long long dist = rezolva(0, n - 1);
	o <<fixed<< dist << '\n';
	return 0;
}