Cod sursa(job #1185048)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 14 mai 2014 21:51:27
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 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 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);
}

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