Cod sursa(job #2087099)

Utilizator andreiulianAndrei andreiulian Data 12 decembrie 2017 21:56:01
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#define inf 10000000000000000000ull;
using namespace std;

pair<int, int> p[100005], c[100005];
int n;

unsigned long long solve(int l, int r);
bool cmp(pair<int, int> a, pair<int, int> b);
unsigned long long dist2(pair<int, int> a, pair<int, int> b);
void merge(int l, int m, int r);

int main() {
	freopen("cmap.in", "r", stdin);
	freopen("cmap.out", "w", stdout);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> p[i].first >> p[i].second;
	}
	sort(p, p + n);
	printf("%.8lf", sqrt(solve(0, n - 1)));
}

unsigned long long solve(int l, int r) {
	vector<pair<int, int>> Y;
	unsigned long long minim = inf;
	if (r - l < 3) {
		for (int i = l; i < r; ++i) {
			for (int j = i + 1; j <= r; ++j) {
				minim = min(minim, dist2(p[i], p[j]));
			}
		}
		sort(p + l, p + r + 1, cmp);
		return minim;
	}
	int m = (l + r) / 2;
	unsigned long long d1 = solve(l, m), d2 = solve(m + 1, r);
	if (d1 > d2) {
		d1 = d2;
	}
	minim = d1;
	merge(l, m, r);
	for (int i = l; i <= r; ++i) {
		if ((unsigned)(p[i].first - p[m].first) * (p[i].first - p[m].first) <= d1) {
			Y.push_back(p[i]);
		}
	}
	for (int i = 0; (unsigned)i < Y.size(); ++i) {
		for (int j = i + 1; (unsigned)j <= Y.size() && j <= i + 7; ++j) {
			minim = min(minim, dist2(Y[i], Y[j]));
		}
	}
	return minim;
}

bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.second < b.second || (a.second == b.second && a.first < b.first)) {
		return 1;
	}
	return 0;
}

unsigned long long dist2(pair<int, int> a, pair<int, int> b) {
	return 1ull * (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

void merge(int l, int m, int r) {
	int k = -1, i, j;
	for (i = l, j = m + 1; i <= m && j <= r;) {
		if (cmp(p[i], p[j])) {
			c[++k] = p[i++];
		} else {
			c[++k] = p[j++];
		}
	}
	while (i <= m) {
		c[++k] = p[i++];
	}
	while (j <= r) {
		c[++k] = p[j++];
	}
	for (i = r; i >= l; --i) {
		p[i] = c[k--];
	}
}