Pagini recente » Cod sursa (job #2864418) | Cod sursa (job #1120355) | Cod sursa (job #1942756) | Cod sursa (job #2835728) | Cod sursa (job #2921951)
#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
#include <unordered_map>
#include <memory>
#include <deque>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
const double EPS = 1e-7;
struct Pt {
int x, y;
Pt(): x(0), y(0) {}
Pt(int x_, int y_): x(x_), y(y_) {}
};
bool cmpPtByX(const Pt& a, const Pt& b) {return a.x != b.x ? a.x < b.x : a.y < b.y;}
bool cmpPtByY(const Pt& a, const Pt& b) {return a.y != b.y ? a.y < b.y : a.x < b.x;}
long long dist(const Pt& a, const Pt& b) {
return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}
void add(deque<Pt>& S, const Pt& n, long long& mind) {
while (S.size() >= 7)
S.pop_front();
for (const auto& p : S)
mind = min(mind, dist(p, n));
S.push_back(n);
}
long long solve(const vector<Pt>::iterator& b, const vector<Pt>::iterator& e) {
assert(e - b >= 2);
if (e - b <= 3) {
long long mind = -1;
sort(b, e, cmpPtByY);
for (auto i = b; i < e; i++)
for (auto j = i + 1; j < e; j++) {
long long d = dist(*i, *j);
if (mind < 0 || d < mind) {
mind = d;
}
}
return mind;
}
auto m = b + (e - b)/2;
long long d = solve(b, m);
d = min(d, solve(m, e));
deque<Pt> S;
double target_x = m->x;
double sqrt_d = sqrt(d);
auto i1 = b;
auto e1 = m ;
auto i2 = m;
auto e2 = e;
auto i = b;
long long mind = d;
while (i1 < e1 || i2 < e2) {
Pt next;
if (i1 < e1 && (i2 >= e2 || i1->x <= i2->x)) {
next = *i1;
++i1;
} else {
next = *i2;
++i2;
}
if (target_x - sqrt_d <= next.x + EPS && next.x - EPS <= target_x + d)
add(S, next, mind);
*i = next;
i++;
}
return mind;
}
int main() {
int N;
f >> N;
vector<Pt> pts(N);
for (int i = 0; i < N; i++) {
f >> pts[i].x >> pts[i].y;
}
sort(pts.begin(), pts.end(), &cmpPtByX);
g << fixed << setprecision(7) << sqrt(solve(pts.begin(), pts.end())) << '\n';
f.close();
g.close();
return 0;
}