Cod sursa(job #2233558)

Utilizator ArkinyStoica Alex Arkiny Data 23 august 2018 16:55:03
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<fstream>
#include<vector>
#include<bitset>
#include<string.h>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<iomanip>
using namespace std;

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

typedef pair<int, int> Point;

int N;

Point points[100010];

double distance(const Point& p1, const Point& p2)
{
	return sqrt((p1.first - p2.first)*(p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second));
}

double closest_pair_of_points(int x,int y)
{
	if (y - x > 3)
	{
		int mid = (x + y) / 2;
		double d1 = closest_pair_of_points(x, mid);

		double d2 = closest_pair_of_points(mid + 1, y);

		double d = min(d1, d2);
		vector<Point> vec;

		for (int i = x; i <= y; ++i)
		{
			
			if (distance(points[i], points[mid]) <= d)
					vec.push_back(make_pair(points[i].second, points[i].first));
			
		}

		sort(vec.begin(), vec.end());
		double f_d = 1 << 20;
		for(int i=0;i<vec.size();++i)
			for (int j = i + 1; j + 8 < vec.size(); ++j)
			{
				f_d = min(f_d, distance(vec[i], vec[j]));
			}
		return min(d,f_d);
	}
	else
	{
		double dist = 1 << 20;
		for(int i=x;i<=y;i++)
			for (int j = i + 1; j <= y; ++j)
			{
				dist = min(dist, distance(points[i], points[j]));
			}
		return dist;
	}
}


int main()
{

	in >> N;

	for (int i = 1; i <= N; ++i)
	{
		int x, y;

		in >> x >> y;

		points[i] = { x,y };
	}

	sort(points + 1, points + N + 1);

	out << fixed << setprecision(6) << closest_pair_of_points(1, N);

	return 0;
}