Cod sursa(job #1025664)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 10 noiembrie 2013 13:48:07
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>

using namespace std;

const int MaxArraySize = 100001;
const long long Inf = 4e18;

long long n, ans, lenght, ind;
pair<long long, long long> vec[MaxArraySize], x[MaxArraySize], y[MaxArraySize];
char *buffer;

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);
}

long long modul(long long val) {
	if (val < 0)
		return -val;
	return val;
}

long long dive_et_imp(int st, int dr, pair<long long, long long> x[],
		pair<long long, long long> y[]) {

	if (st >= dr - 1)
		return Inf;

	if (dr - st == 2) {
		if (y[st] > y[st + 1])
			swap(y[st], y[st + 1]);
		return dist(x[st], x[st + 1]);
	}

	long long sol, mij, i, j, m = 0;

	mij = st + (dr - st) / 2;
	sol = min(dive_et_imp(st, mij, x, y), dive_et_imp(mij, dr, x, y));

	sort(y + st, y + dr);

	for (i = st; i < dr; ++i)
		if (sol >= modul(y[i].second - x[mij].first))
			vec[m++] = y[i];

	for (i = 0; i < m - 1; ++i)
		for (j = i + 1; j < m && j - i < 8; ++j)
			sol = min(sol, dist(vec[i], vec[j]));

	return sol;
}

long long get_number() {

	long long val = 0;

	while (ind < lenght && !(buffer[ind] >= '0' && buffer[ind] <= '9'))
		++ind;

	while (ind < lenght && buffer[ind] >= '0' && buffer[ind] <= '9') {
		val = val * 10 + buffer[ind] - '0';
		++ind;
	}

	return val;
}

int main() {

	int i;

	FILE *f = fopen("cmap.in", "rb");
	fseek(f, 0L, SEEK_END);
	lenght = ftell(f);
	rewind(f);
	buffer = (char*) calloc(1, lenght + 1);
	fread(buffer, lenght, 1, f);
	fclose(f);

	n = get_number();

	for (i = 0; i < n; ++i) {
		x[i].first = get_number();
		x[i].second = get_number();
	}

	sort(x, x + n);

	for (i = 0; i < n; ++i)
		y[i] = make_pair(x[i].second, x[i].first);

	ans = dive_et_imp(0, n, x, y);

	FILE *g = fopen("cmap.out", "w");
	fprintf(g, "%lf", sqrt(ans));
	fclose(g);

	return 0;
}