Cod sursa(job #1185058)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 14 mai 2014 22:03:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <algorithm>
#include <cmath>
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

typedef long long i64;
const i64 inf = 1LL << 61;

const int MaxN = 100005;
int n;
pair<int, int> v[MaxN], org[MaxN], aux[MaxN];

inline i64 abs(i64 a) {
	return max(-a, a);
}

inline i64 dist(const pair<int, int> &a, const pair<int, int> &b) {
	return 1LL * (a.first - b.first) * (a.first - b.first) + 1LL * (a.second - b.second) * (a.second - b.second);
}

void merge(int left, int right) {
	int mid = (left + right) / 2, p1 = left, p2 = mid + 1, len = 0;
	
	while (p1 <= mid || p2 <= right)
		if (p1 > mid) 
			aux[++len] = v[p2++];
		else if (p2 > right)
			aux[++len] = v[p1++];
		else if (v[p1].second < v[p2].second)
			aux[++len] = v[p1++];
		else
			aux[++len] = v[p2++];
	
	for (int i = left, j = 1; i <= right; ++i, ++j)
		v[i] = aux[j];
}


i64 make(int left, int right) {
	i64 res = inf;
	if (right - left <= 2) {
		for (int i = left; i <= right; ++i)
			for (int j = i + 1; j <= right; ++j)
				res = min(res, dist(v[i], v[j]));
		sort(v + left, v + 1 + right, 
			[&] (const pair<int, int> &a, const pair<int, int> &b) {
				return a.second < b.second;
			}
		);
		return res;
	}
	
	int mid = (left + right) / 2;
	res = min(make(left, mid), make(mid + 1, right));
	
	merge(left, right);
	
	int len = 0;
	for (int i = left; i <= right; ++i)
		if (abs(v[i].first - org[mid].first) <= res)
			aux[++len] = v[i];
	
	for (int i = 1; i < len; ++i)
		for (int j = i + 1, cnt = 1; cnt <= 7; ++j, ++cnt)
			res = min(res, dist(aux[i], aux[j]));
	
	return res;
}

int main() {
	fin >> n;
	for (int i = 1; i <= n; ++i)
		fin >> v[i].first >> v[i].second;
	sort(v + 1, v + 1 + n, 
		[&] (const pair<int, int> &a, const pair<int, int> &b) {
			if (a.first == b.first)
				return a.second < b.second;
			return a.first < b.first;
		}
	);
	
	for (int i = 1; i <= n; ++i)
		org[i] = v[i];
	
	fout << fixed << setprecision(6) << sqrt(make(1, n)) << '\n';
	fin.close(); fout.close(); return 0;
}