Cod sursa(job #2233591)

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

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

typedef pair<long long, long long> Point;

int N;

Point points[100010];

vector<Point> mrg[100010 * 4];

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, int k)
{
	if (y - x > 3)
	{
		int mid = (x + y) / 2;
		double d1 = closest_pair_of_points(x, mid, k*2);

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

		merge(mrg[k * 2].begin(), mrg[k * 2].end(), mrg[k * 2 + 1].begin(), mrg[k * 2 + 1].end(), back_inserter(mrg[k]));

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

		for (int i=0;i<mrg[k].size();++i)
		{
			
			if (abs(points[mid].first - mrg[k][i].second) <= d)
					vec.push_back(make_pair(mrg[k][i].second, mrg[k][i].first));
			
		}


		double f_d = 1LL<<60;
		for(int i=0;i<vec.size();++i)
			for (int j = i + 1; j < min(i + 8, (int)vec.size()); ++j)
			{
				f_d = min(f_d, distance(vec[i], vec[j]));
			}
		mrg[k * 2].clear();
		mrg[k * 2 + 1].clear();

		mrg[k * 2].resize(0);
		mrg[k * 2 + 1].resize(0);
		return min(d,f_d);
	}
	else
	{
		for (int i = x; i <= y; ++i)
			mrg[k].push_back(make_pair(points[i].second, points[i].first));

		sort(mrg[k].begin(), mrg[k].end());

		double dist =1ll<<60;
		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.sync_with_stdio(false);
	in.tie(NULL);
	
	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, 1);

	return 0;
}