Cod sursa(job #479555)

Utilizator razvi9Jurca Razvan razvi9 Data 24 august 2010 14:41:55
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const int BUFSIZE = 1000000;
char buf[BUFSIZE];

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

typedef pair<int, int> point;
#define y first
#define x second

inline double dist(const point &a, const point &b)
{
	return sqrt((double)(a.x - b.x)*(double)(a.x - b.x) + (double)(a.y - b.y)*(double)(a.y - b.y));
}

double distOnLine(const vector<point> &p)
{
	double best = dist(p[0], p[1]), temp;
	for(unsigned int i=2;i<p.size();++i)
	{
		temp = dist(p[i - 1], p[i]);
		if(temp < best)
			best = temp;
	}
	return best;
}

double distBrut(const vector<point> &p)
{
	double best = dist(p[0], p[1]), temp;
	for(unsigned int i=0;i<p.size();++i)
		for(int j=i+1;j<p.size();++j)
			if((temp = dist(p[i], p[j])) < best)
				best = temp;
	return best;
}

double dist(const vector<point> &p, int min, int max)
{
	if (p.size() < 2)
		return 1e20;
	if (p.size() < 5)
		return distBrut(p);

	if(min == max)
		return distOnLine(p);

	int mij = (min + max) / 2;
	vector<point> left, right;
	for(unsigned int i=0;i<p.size();++i)
		if(p[i].x <= mij)
			left.push_back(p[i]);
		else
			right.push_back(p[i]);

	double dl = dist(left, min, mij),
		dr = dist(right, mij + 1, max);
	left.clear(), right.clear();

	double d = std::min(dl, dr);
	for(unsigned int i=0;i<p.size();++i)
		if(abs(p[i].x - mij) < d)
			left.push_back(p[i]);

	double temp;
	for(unsigned int i=0;i<left.size();++i)
	{
		for (unsigned int j = i + 1; j < left.size() && p[i].y + d > p[j].y; ++ j)
			if ((temp = dist(p[i], p[j])) < d)
				d = temp;
	}

	return d;
}

int main()
{
	cin.rdbuf()->pubsetbuf(buf, BUFSIZE);

	int n, min = 0x7fffffff, max = 0x8fffffff;
	cin >> n;
	vector<point> p(n);
	for(int i=0;i<n;++i)
	{
		cin >> p[i].x >> p[i].y;
		if(p[i].x < min)
			min = p[i].x;
		if(p[i].x > max)
			max = p[i].x;
	}

	std::sort(p.begin(), p.end());
	double d = dist(p, min, max);
	cout << setprecision(20) << d << endl;

	return 0;
}