Pagini recente » Cod sursa (job #2311851) | Cod sursa (job #1073875) | Cod sursa (job #2536741) | Cod sursa (job #838648) | Cod sursa (job #1556612)
#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 cmpx {
bool operator () (const Point& a, const Point& b) const {
return real(a) < real(b)
|| real(a) == real(b) && imag(a) < imag(b);
}
};
struct cmpy {
bool operator () (const Point& a, const Point& b) const {
return imag(a) < imag(b)
|| imag(a) == imag(b) && real(a) < real(b);
}
};
double sqdist(const Point& a, const Point& b) {
return norm(b-a);
}
int main() {
ios::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(), cmpx());
set<Point,cmpy> sorty;
double best = 4*oo;
double sqbest = pow(best,2);
int lox = 0;
sorty.emplace(oo, oo+best);
sorty.emplace(oo, -oo-best);
for (int i = 0; i < n; i++) {
while (real(P[lox]) <= real(P[i])-best) {
sorty.erase(P[lox]);
lox++;
}
auto res = sorty.insert(P[i]);
for (auto it = next(res.first); imag(*it) < imag(P[i])+best; ++it) {
if (sqbest > sqdist(P[i], *it)) {
sqbest = sqdist(P[i], *it);
best = sqrt(sqbest);
}
}
for (auto it = prev(res.first); imag(*it) > imag(P[i])-best; --it) {
if (sqbest > sqdist(P[i], *it)) {
sqbest = sqdist(P[i], *it);
best = sqrt(sqbest);
}
}
}
printf("%.6f\n", best);
}