Cod sursa(job #1396718)

Utilizator Aavatar36Russu Vadim Aavatar36 Data 22 martie 2015 21:16:44
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <set>
#include <iomanip>
std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
int N;
std::vector<std::pair<long long int, long long int> > v;
std::set<std::pair<long long int, long long int> > events;

int main() {
	fin >> N;
	for (int i = 0; i < N; ++i)
	{
		long long int a, b;
		fin >> a >> b;
		v.push_back(std::make_pair(a, b));
		events.insert(std::make_pair(a, b));
	}
	std::sort(v.begin(), v.end());
	events.insert(*v.begin());
	double best = sqrt((v[0].first - v[1].first) * (v[0].first - v[1].first) + (v[0].second - v[1].second) * (v[0].second - v[1].second));
	for (std::vector<std::pair<long long int, long long int> >::iterator it = v.begin(); it != v.end() - 1; ++it)
	{
		double cur = sqrt((it->first - (it + 1)->first) * (it->first - (it + 1)->first) + (it->second - (it + 1)->second) * (it->second - (it + 1)->second));
		if (cur < best) best = cur;
	}


	for (std::vector<std::pair<long long int, long long int> >::iterator i = v.begin(); i != v.end(); ++i)
	{
		for (std::set<std::pair<long long int, long long int> >::iterator it = events.lower_bound(std::make_pair(i->first - best, i->second - best));
		        it != events.upper_bound(std::make_pair(i->first, i->second + best)) ; ++it) {
			if ((i->first != it->first) && (it->second != i->second)) {
				double cur = sqrt((i->first - it->first) * (i->first - it->first) + (i->second - it->second) * (i->second - it->second));
				if (cur < best) best = cur;
			}
		}
	}

	fout << std::setprecision(20) << best;
	return 0;
}