Pagini recente » Cod sursa (job #498009) | Cod sursa (job #3222776) | Cod sursa (job #1344672) | Cod sursa (job #1782390) | Cod sursa (job #2472544)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define sz(x) (int)((x).size())
#define all(x) (x).begin(),(x).end()
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define eb emplace_back
typedef pair< int, int > pii;
typedef pair< long long, long long > pll;
typedef long long ll;
typedef unsigned long long ull;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< ll > vll;
typedef vector< vll > vvll;
typedef vector< pii > vpii;
typedef vector< vpii > vvpii;
typedef vector< pll > vpll;
typedef long double ld;
typedef vector< ld > vld;
const ll MOD2 = 1e9 + 7;
const int MOD = 1e9 + 7;
const ull infull = numeric_limits<unsigned long long>::max();
void fix(int &x, ll MOD) {
x = (x % MOD);
if(x < 0) x += MOD;
return;
}
ll lgput(ll a, ll b, ll MOD) {
ll ret = 1;
a %= MOD;
while(b) {
if(b&1) ret = ret*a % MOD;
a = a*a % MOD;
b >>= 1;
}
return ret;
}
ll inv(ll a, ll MOD) {
return lgput(a, MOD-2, MOD);
}
struct f {
int a, b;
f(int _a = 0, int _b = 0) : a(_a) ,b(_b) {}
ll eval(int x) {
return 1ll*x*a + b;
}
};
int binarySearch(int x, vi &v) {
int pos = 0;
int l = 1, r = sz(v);
while(l <= r) {
int m = l + r >> 1;
if(v[m] <= x) {
pos = m;
l = m + 1;
} else {
r = m - 1;
}
}
return pos;
}
const int MAXN = 1e5 + 10;
struct p{
int x, y;
};
p v[MAXN];
p v2[MAXN];
bool cmpx(p a, p b) {
return a.x == b.x ? a.x < b.x : a.x < b.x;
}
bool cmpy(p a, p b) {
return a.y < b.y;
}
ll get(p a, p b) {
ll nowDist = 1ll*(a.x - b.x)*(a.x - b.x) + 1ll*(a.y - b.y)*(a.y - b.y);
return nowDist;
}
ll divide(int st, int dr) {
if(dr <= st + 2) {
ll ans = 1e18;
for(int i = st; i <= dr; ++i) {
for(int j = i + 1; j <= dr; ++j) {
ans = min(ans, get(v[i], v[j]));
}
}
sort(v + st, v + dr + 1, cmpy);
return ans;
}
int mid = st + dr >> 1;
int midval = v[mid].x;
ll ans = min(divide(st, mid), divide(mid + 1, dr));
merge(v + st, v + mid + 1, v + mid + 1, v + dr + 1, v2 + st, cmpy);
int cnt = 0;
for(int i = st; i <= dr; ++i) {
v[i] = v2[i];
if(1ll*(v[i].x - midval)*(v[i].x - midval) <= ans) v2[++cnt] = v[i];
}
for(int i = 1; i <= cnt; ++i) {
for(int j = i + 1; j <= cnt && 1ll*(v2[i].x - v2[j].x)*(v2[i].x - v2[j].x) <= ans; ++j) {
ans = min(ans, get(v2[i], v2[j]));
}
}
return ans;
}
int main() {
#ifdef BLAT
freopen("stdin", "r", stdin);
freopen("stderr", "w", stderr);
#else
FO(cmap);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(12);
srand(time(NULL));
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, cmpx);
ll ans = divide(1, n);
cout << setprecision(12) << fixed << sqrt(ans) << '\n';
return 0;
}