Cod sursa(job #941693)

Utilizator forgetHow Si Yu forget Data 19 aprilie 2013 14:11:10
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

struct point
{
	int x, y;
};

bool compx(const point& a, const point& b)
{
	return a.x < b.x;
}

bool compy(const point& a, const point& b)
{
	return a.y < b.y;
}

double dist(const point& a, const point& b)
{
	return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
	
vector<point> p, q;
double d = 2e9;
point inf;

void findclosest(int l, int r)
{
	vector<point> a;
	if (r-l < 3) {
		for (int i = l+1; i <= r; ++i)
			for (int j = l; j < i; ++j)
				d = min(d, dist(p[i],p[j]));
		sort(q.begin()+l, q.begin()+r+1, compy);
		return;
	}
	int m = (l+r)/2;
	int median = p[m].x;
	vector<point> b1, b2;
	findclosest(l,m);
	findclosest(m+1,r);
	for (int i = l; i <= m; ++i)
		if (median-q[i].x < d)
			b1.push_back(q[i]);
	for (int i = m+1; i <= r; ++i)
		if (q[i].x-median < d)
			b2.push_back(q[i]);
	int i(0), j(0), b1s = b1.size(), b2s = b2.size();
	b1.push_back(inf);
	b2.push_back(inf);
	while (i < b1s && j < b2s) {
		d = min(d, dist(b1[i],b2[j]));
		if (b1[i].y < b2[j].y)
			d = min(d, dist(b1[i++],b2[j+1]));
		else
			d = min(d, dist(b1[i+1],b2[j++]));
	}
	inplace_merge(q.begin()+l, q.begin()+m+1, q.begin()+r+1,compy);
}

int main()
{
	ifstream fin("cmap.in");
	ofstream fout("cmap.out");
	int n;
	fin >> n;
	p.resize(n);
	for (int i = 0; i < n; ++i)
		fin >> p[i].x >> p[i].y;
	sort(p.begin(), p.end(), compx);
	q = p;
	inf.y = 2e9;
	findclosest(0, n-1);
	fout.precision(6);
	fout << fixed << d;
	return 0;
}