Cod sursa(job #2072577)

Utilizator AndreiukAndrei C Andreiuk Data 21 noiembrie 2017 22:54:33
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#define x first
#define y second

using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");
const int MAXN = 100002;
const long long inf = 3e18;

pair <int, int> a[MAXN], b[MAXN], aux[MAXN];

long long getDistance( pair <int, int> A, pair <int, int> B ) {
	return 1LL * (A.x-B.x) * (A.x-B.x) + 1LL * (A.y-B.y) * (A.y-B.y);
}

long long get ( int begin, int end ) {
	if (begin == end)
		return inf;
	if (end - begin == 1) {
		if (b[end] < b[begin])
			swap(b[end], b[begin]);
		return getDistance(b[begin], b[end]);
	}

	int middle = (begin+end)>>1;
	long long minDistance = min(get(begin, middle), get(middle+1, end));

	merge(b + begin, b + middle + 1, b + middle + 1, b + end + 1, aux);
	copy(aux, aux + (end - begin + 1), b + begin);

	int k = 0;
	for(int i=begin; i<=end; ++i)
		if (abs(b[i].y - a[middle].x) <= minDistance)
			aux[k++] = b[i];

	for(int i=0; i<k; ++i)
		for(int j=i+1; j<k && j <= i + 8; ++j)
			minDistance = min(minDistance, getDistance(aux[i], aux[j]));


	return minDistance;
}

int main()
{
	int i, n;
	f>>n;
	for (i=1; i<=n; ++i)
		f >> a[i].x >> a[i].y;
	sort(a + 1, a + n + 1);
	for (i=1; i<=n; ++i)
		b[i] = make_pair(a[i].y, a[i].x);

    g.setf(ios::fixed, ios::floatfield);
	g.precision(6);
	g << sqrt( get(1, n) ) << "\n";
	return 0;
}