Cod sursa(job #1690872)

Utilizator Aavatar36Russu Vadim Aavatar36 Data 16 aprilie 2016 01:22:35
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#define pdd std::pair<double, double>

#include <fstream>
#include <set>
#include <cmath>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <limits>

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

struct by_y {
	bool operator()(const pdd a, const pdd b) const {
		return a.second != b.second ? a.second < b.second : a.first < b.first;
	}
};

double getDistance(const pdd a, const pdd b) {
	return std::sqrt((a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second));
}

int main() {
	int N;
	fin >> N;

	std::set<pdd, by_y> candidates;
	std::vector<pdd> pointsSorted;

	for (int i = 0; i < N; i++) {
		int a, b;
		fin >> a >> b;
		pointsSorted.push_back({ a, b });
	}

	std::sort(pointsSorted.begin(), pointsSorted.end());

	double minDistance = std::numeric_limits<double>::infinity();

	std::vector<pdd>::iterator leftMost = pointsSorted.begin();

	for (std::vector<pdd>::iterator it = pointsSorted.begin(); it != pointsSorted.end(); it++) {
		pdd current = *it;
		while (current.first - leftMost->first > minDistance) {
			candidates.erase(*leftMost);
			leftMost++;
		}
		std::set<pdd, by_y>::iterator rangeFrom = candidates.lower_bound(std::make_pair(current.first, current.second - minDistance));
		std::set<pdd, by_y>::iterator rangeEnd = candidates.upper_bound(std::make_pair(current.first, current.second + minDistance));

		for (std::set<pdd, by_y>::iterator it1 = rangeFrom; it1 != rangeEnd; it1++) {
			double tempDistance = getDistance(current, *it1);
			if (tempDistance < minDistance) {
				minDistance = tempDistance;
			}
		}

		candidates.insert(current);
	}

	fout << std::fixed << std::setprecision(6) << minDistance << "\n";
	return 0;
}