Cod sursa(job #1690821)

Utilizator Aavatar36Russu Vadim Aavatar36 Data 15 aprilie 2016 21:30:08
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <set>
#include <cmath>
#include <iomanip>

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


double getDistance(const std::pair<double, double> a, const std::pair<double, double> 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<std::pair<double, double> > pointMap;

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

	double minDistance = getDistance(*pointMap.begin(), *(--pointMap.end()));

	for (std::set<std::pair<double, double> >::iterator it = pointMap.begin(); it != (--pointMap.end()); it++) {
		std::set<std::pair<double, double> >::iterator it2 = it;
		it2++;
		double tempDist = getDistance(*it, *it2);
		if (tempDist < minDistance) {
			minDistance = tempDist;
		}
	}

	for (std::set<std::pair<double, double> >::iterator it = pointMap.begin(); it != (--pointMap.end()); it++) {
		std::set<std::pair<double, double> >::iterator rangeBegin = pointMap.lower_bound({ it->first - minDistance, 0 });
		std::set<std::pair<double, double> >::iterator rangeEnd = pointMap.upper_bound({ it->first + minDistance, 0 });

		for (std::set<std::pair<double, double> >::iterator it2 = rangeBegin; it2 != rangeEnd; it2++) {
			if (*it == *it2) {
				continue;
			}
			double tempDist = getDistance(*it, *it2);
			if (tempDist < minDistance) {
				minDistance = tempDist;
			}
		}
	}
	fout << std::fixed << std::setprecision(6) << minDistance << "\n";
	return 0;
}