Cod sursa(job #1590446)

Utilizator howsiweiHow Si Wei howsiwei Data 5 februarie 2016 08:25:40
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <complex>
using namespace std;
typedef complex<double> Point;
const double oo = 2e9;

struct cmpxy {
	bool operator () (const Point& a, const Point& b) const {
		return real(a) < real(b);
	}
};

struct cmpy {
	bool operator () (const Point& a, const Point& b) const {
		return imag(a) < imag(b);
	}
};

double sqd(const Point& a, const Point& b) {
	return norm(b-a);
}

int main() {
	cin.sync_with_stdio(false);
	freopen("cmap.in", "r", stdin);
	freopen("cmap.out", "w", stdout);
	int n;
	cin >> n;
	vector<Point> P(n);
	for (int i = 0; i < n; i++) {
		double x, y;
		cin >> x >> y;
		P[i] = {x,y};
	}
	sort(P.begin(), P.end(), cmpxy());

	set<Point,cmpy> ordy;
	double best = 4*oo;
	double sqbest = pow(best,2);
	int lx = 0;
	ordy.emplace(oo, oo+best);
	ordy.emplace(oo, -oo-best);

	for (int i = 0; i < n; i++) {
		while (real(P[lx]) <= real(P[i])-best) {
			ordy.erase(P[lx]);
			lx++;
		}
		auto it0 = ordy.insert(P[i]).first;
		for (auto it = next(it0); imag(*it) < imag(P[i])+best; ++it) {
			if (sqbest > sqd(P[i], *it)) {
				sqbest = sqd(P[i], *it);
				best = sqrt(sqbest);
			}
		}
		for (auto it = prev(it0); imag(*it) > imag(P[i])-best; --it) {
			if (sqbest > sqd(P[i], *it)) {
				sqbest = sqd(P[i], *it);
				best = sqrt(sqbest);
			}
		}
	}
	printf("%.6f\n", best);
}