Pagini recente » Cod sursa (job #952951) | Cod sursa (job #2560918) | Cod sursa (job #2052318) | Cod sursa (job #476741) | Cod sursa (job #3120870)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
ifstream in("cmap.in");
ofstream out("cmap.out");
#define cin in
#define cout out
#endif // LOCAL
struct pt {
int x, y;
};
bool cmp_x(pt a, pt b) {
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool cmp_y(pt a, pt b) {
if(a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
int64_t euclid(pt a, pt b) {
return (1LL * a.x - b.x) * (1LL * a.x - b.x) + (1LL * a.y - b.y) * (1LL * a.y - b.y);
}
int64_t line_dist(pt a, int d) {
return (1LL * a.x - d) * (1LL * a.x - d);
}
const int64_t max_dist = 8e18 + 17;
int64_t dist = max_dist;
const int BULAN = 7;
vector<pt> merge_y(vector<pt> a, vector<pt> b) {
vector<pt> ret;
std::merge(a.begin(), a.end(),
b.begin(), b.end(),
std::back_inserter(ret),
cmp_y);
return ret;
}
vector<pt> solve(vector<pt> pts) {
if(pts.size() <= BULAN) {
for(int i = 0; i < pts.size(); i++) {
for(int j = i + 1; j < pts.size(); j++) {
dist = min(dist, euclid(pts[i], pts[j]));
}
}
sort(pts.begin(), pts.end(), cmp_y);
return pts;
}
int mid = pts.size() / 2;
vector<pt> lpt, rpt;
for(int l = 0; l < mid; l++) lpt.push_back(pts[l]);
for(int r = mid; r < pts.size(); r++) rpt.push_back(pts[r]);
int dif_x = lpt.back().x;
lpt = solve(lpt); rpt = solve(rpt);
pts = merge_y(lpt, rpt);
vector<pt> close_line;
for(auto e : pts) if(line_dist(e, dif_x) <= dist) close_line.push_back(e);
for(int i = 0; i < close_line.size(); i++) {
for(int j = i + 1; j <= i + BULAN && j < close_line.size(); j++) {
dist = min(dist, euclid(close_line[i], close_line[j]));
}
}
return pts;
}
int main()
{
#ifndef LOCAL
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif // LOCAL
int n; cin >> n;
vector<pt> v(n); for(auto &e : v) cin >> e.x >> e.y;
sort(v.begin(), v.end(), cmp_x);
auto _discard = solve(v);
cout << fixed << setprecision(8) << sqrt(dist) << endl;
return 0;
}