Cod sursa(job #1185043)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 14 mai 2014 21:40:25
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 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], aux[MaxN];

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

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]));
		return res;
	}
	
	int mid = (left + right) / 2;
	res = min(make(left, mid), make(mid + 1, right));
	
	sort(v + left, v + 1 + right, 
		[&] (const pair<int, int> &a, const pair<int, int> &b) {
			return a.second < b.second;
		}
	);
	
	for (int i = left; i <= right; ++i)
		for (int j = i + 1, cnt = 0; cnt <= 7 && j <= right; ++j)
			res = min(res, dist(v[i], v[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;
		}
	);
	
	fout << fixed << setprecision(6) << sqrt(make(1, n)) << '\n';
	fin.close(); fout.close(); return 0;
}