Pagini recente » Cod sursa (job #2063095) | Cod sursa (job #1976668) | Cod sursa (job #2627537) | Cod sursa (job #794470) | Cod sursa (job #2883559)
#include <bits/stdc++.h>
#define dbg(x) if (COND) {cout << #x << "=" << x << "\n"; }
#define dbgvp(x) if (COND) {cout << #x << ": "; for (auto k : x) {cout << "{" << k.first << "," << k.second << "} "; }cout << "\n";}
#define sep if(COND) cout << "\n-------------------------\n";
#define dbgp(x) if (COND) {cout << #x << "={" << x.first << "," << x.second << "}\n";}
using namespace std;
bool COND = true;
#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("cmap.in");
ofstream out("cmap.out");
#endif // LOCAL
typedef pair<int,int> pp;
int n;
vector<pp> pt;
double modulo(double x) {
if ( x > 0) return x;
return -x;
}
double sq(double x) {
return x * x;
}
double dist(pp A, pp B) {
return sqrt( sq( A.first - B.first ) + sq(A.second - B.second ) );
}
double solve(int l, int r) {
if (r - l + 1 <= 1) {
return 1 / .0;
}
int mid = (l + r) / 2;
int midx = pt[mid].first; ///any points on the line are in the first half
// dbg(mid);
// dbg(midx);
double s = min(solve(l , mid) , solve(mid + 1 , r));
//dbg(s);
/*
if (l == 1 && r == n) {
dbg(mid);
dbg(solve(l , mid));
dbg(solve(mid + 1 , r));
dbg(s);
}*/
vector<pair<int,int>> y;
for (int i = l; i <= r; i++) {
if ( modulo(midx - pt[i].first) <= s) {
y.push_back(pt[i]);
}
}
sort(y.begin(), y.end() , [&](pp A, pp B) {
return A.second < B.second;
}
);
// dbgvp(y);
for (int i = 0; i < y.size(); i++) {
for (int j = i + 1; j < min((int)y.size() , i + 8); j++ ) {
s = min(s , dist(y[i] , y[j]));
// dbg(i);
// dbg(j);
// dbgp(y[i]);
// dbgp(y[j]);
// dbg(dist(y[i] , y[j]));
// dbg(s);
// sep;
}
}
// i//f ( l == 1 && r == n) {
// dbg(s);
//}
return s;
}
int main() {
in >> n;
pt.resize(n + 1);
for (int i = 1; i <= n; i++) {
int x,y;
in >> x >> y;
pt[i] = {x,y};
}
sort(pt.begin() + 1, pt.end());///sort after x
// dbgvp(pt);
out << fixed << setprecision(12) << solve(1 , n) << "\n";
}