Cod sursa(job #650453)

Utilizator nandoLicker Nandor nando Data 18 decembrie 2011 10:21:51
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

#define x first
#define y second

typedef long long int64;
typedef pair<int64, int64> point;

const int maxn = 100100;
const int64 inf = 1e18;

vector<point> x, y;
int n;

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

int64 find(int left, int right)
{
	if (right - left <= 1) {
		return inf;
	}

	if (right - left == 2) {
		if (y[left] > y[left + 1]) {
			swap(y[left], y[left + 1]);
		}
		
		return dist(y[left], y[left + 1]);
	}	
	
	int mdl = (left + right) >> 1;
	int64 s = min(find(left, mdl), find(mdl, right));

	vector<point> v(right - left);
	merge(y.begin() + left, y.begin() + mdl, y.begin() + mdl, y.begin() + right, v.begin());
	copy(v.begin(), v.end(), y.begin() + left);

	v.clear();
	
	for (int i = left; i < right; ++i) {
		if (abs(y[i].y - x[mdl].x) <= s) {
			v.push_back(y[i]);
		}
	}

	for (int i = 0; i < (int)v.size() - 1; ++i) {
		for (int j = i + 1; j < min((int)v.size(), i + 8); ++j) {
			s = min(s, dist(v[i], v[j]));
		}
	}
	
	return s;
}

int main()
{
	FILE* fin = fopen("cmap.in", "r");
	FILE* fout = fopen("cmap.out", "w");

	fscanf(fin, "%d\n", &n);
	
	x.resize(n);
	y.resize(n);

	for (int i = 0; i < n; ++i) {
		fscanf(fin, "%d %d\n", &x[i].x, &x[i].y);
	}

	sort(x.begin(), x.end());
	copy(x.begin(), x.end(), y.begin());

	printf("%.6lf", sqrt((long double)find(0, n)));

	fclose(fin);
	fclose(fout);
	return 0;
}