Cod sursa(job #2272417)

Utilizator gundorfMoldovan George gundorf Data 30 octombrie 2018 10:10:09
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#define Nmax 1005
#define MINF 10000000
#include <utility>
using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");


double distance(pair<int, int> p1, pair<int, int> p2)
{
	return 1.0*(sqrt((p1.first - p2.first)*(p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second)));
}

int n;
pair<int, int> v[Nmax];

double Calcul(int ps, int pf, vector <pair<int, int>> Y)
{

	if (pf - ps + 1 <= 3)
	{
		double mini = MINF;
		for (int i = ps; i<pf; i++)
			for (int j = i + 1; j <= pf; j++)
				if (distance(v[i], v[j])<mini) mini = distance(v[i], v[j]);
		return mini;
	}
	int x_dr;//ecuatia dreptei de despartire
	int mij;
	mij = (pf - ps + 1) / 2;
	x_dr = v[(pf - ps + 1) / 2].first;
	vector <pair<int, int>> dy1;//punct punctele sortate dupa y, situate in stanga dreptei de despartire
	vector <pair<int, int>> dy2;

	for (int i = ps; i <= pf; i++)
		if (v[i].first <= x_dr) dy1.push_back(v[i]);
		else dy2.push_back(v[i]);

		double min1 = Calcul(ps, mij, dy1);
		double min2 = Calcul(mij + 1, pf, dy2);
		min2 = min(min2, min1);

		double min3 = MINF;

		vector <pair<int, int>>YIntersectat;

		for (pair<int, int> aux : Y)
			if (abs(aux.first - x_dr) <= min2) YIntersectat.push_back(aux);

		for (int i = 0; i<YIntersectat.size(); i++)
			for (int j = i + 1; j <= i + 7; j++)
				if(j<YIntersectat.size())
				if (distance(YIntersectat[i], YIntersectat[j])<min3)
					min3 = distance(YIntersectat[i], YIntersectat[j]);

		return (min(min3, min2));
}
bool cmp(pair<int, int>p1, pair<int, int>p2)
{
	return (p1.first < p2.first);
}
int main()
{
	vector <pair<int, int>> Y;
	fin >> n;
	for (int i = 1; i <= n; i++)
	{
		int x, y;
		fin >> x >> y;
		pair<int, int> aux;
		aux.first = x;
		aux.second = y;
		v[i] = aux;
		Y.push_back(aux);
	}
	//fout<<Y[56].first;
	sort(v + 1, v + n + 1, cmp);
	fout << Calcul(1, n, Y);
	return 0;
}