Cod sursa(job #948503)

Utilizator howsiweiHow Si Wei howsiwei Data 10 mai 2013 17:55:54
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <cmath>
using namespace std;

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

struct point
{
	double x;
	double y;

	point() { }
	point( double _x, double _y ) : x(_x), y(_y) { }

	bool operator < ( const point & a ) const {
		return x != a.x ? x < a.x : y < a.y;
	}
};

struct cmpy
{
	bool operator() (const point & a, const point & b) const {
		return a.y != b.y ? a.y < b.y : a.x < b.x;
	}
};

double get_dist_sqr(const point & a, const point & b)
{
	return pow(a.x-b.x, 2) + pow(a.y-b.y, 2);
}

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

	vector<point> P(n);
	for (int i = 0; i < n; ++i) {
		fin >> P[i].x >> P[i].y;
	}
	sort( P.begin(), P.end() );

	set<point, cmpy> sorty;
	double best = 1e10;
	int lox = 0;

	for (int i = 0; i < n; ++i) {
		while (P[lox].x <= P[i].x - best) { // require best > 0 
			sorty.erase(P[lox]);
			++lox;
		}

		set<point, cmpy>::iterator lo = sorty.upper_bound( point(P[i].x, P[i].y - best) ); // require best > 0 
		set<point, cmpy>::iterator hi = sorty.lower_bound( point(P[i].x, P[i].y + best) );
		double best_sqr = pow(best, 2);

		for (set<point, cmpy>::iterator it = lo; it != hi; ++it) {
			best_sqr = min( best_sqr, get_dist_sqr(P[i], *it) );
		}
		best = sqrt(best_sqr);

		sorty.insert(P[i]);
	}

	fout.precision(15);
	fout << fixed << best;
	return 0;
}