Cod sursa(job #1237718)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 4 octombrie 2014 18:38:19
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define DIM 100005
#define INF (1LL << 62)
#define infile "cmap.in"
#define outfile "cmap.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

pair<long long, long long> x[DIM], y[DIM], z[DIM];

int n;

long long dist(pair<long long, long long> a, pair<long long, long long> b) {
	return (a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second);
}

inline long long modul(long long a) {
	return (a > 0 ? a : -a);
}

long long solve(int st, int dr) {
	if (st == dr)
		return INF;
	if (dr - st + 1 == 2) {
		if (y[st] > y[st + 1]) {
			pair<long long, long long> tmp;
			tmp = y[st];
			y[st] = y[st + 1];
			y[st + 1] = tmp;
		}
		return dist(x[st], x[st + 1]);
	}
	int mid = (st + dr) / 2;
	long long sol = std::min(solve(st, mid), solve(mid + 1, dr));
	int i = st, j = mid + 1;
	int nn = 0;
	while (i <= mid && j <= dr)
		if (y[i] <= y[j])
			z[++nn] = y[i++];
		else
			z[++nn] = y[j++];
	for (; i <= mid; ++i)
		z[++nn] = y[i];
	for (; j <= dr; ++j)
		z[++nn] = y[j];
	for (i = st; i <= dr; ++i)
		y[i] = z[i - st + 1];
	nn = 0;
	for (i = st; i <= dr; ++i)
	if (modul(y[i].second - x[mid].first) <= sol)
		z[++nn] = y[i];
	for (i = 1; i <= nn; ++i)
	for (j = i + 1; j <= nn && j <= i + 7; ++j)
		sol = std::min(sol, dist(y[i], y[j]));
	return sol;
}

int main() {
	f >> n;
	for (int i = 1; i <= n; ++i)
		f >> x[i].first >> x[i].second;
	sort(x + 1, x + n + 1);
	for (int i = 1; i <= n; ++i) {
		y[i].second = x[i].first;
		y[i].first = x[i].second;
	}
	g << setprecision(6) << fixed << sqrt(solve(1, n));
	return 0;
}