Pagini recente » Cod sursa (job #381527) | Cod sursa (job #500488) | Cod sursa (job #2062374) | Cod sursa (job #853449) | Cod sursa (job #2922438)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vt vector
#define pb push_back
#define em emplace
#define emb emplace_back
#define all(x) x.begin(), x.end()
#define all1(x) x.begin() + 1, x.end()
#define sz(x) (int)(x).size()
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T> void re(vt <T>& x);
template <class T> void re(T& x) {
cin >> x;
}
template <class H, class... T> void re(H &x, T&... y) {
re(x); re(y...);
}
template <class T> void re(vt <T>& x) {
for(auto& it : x)
re(it);
}
template <class T> void wr(T x) {
cout << x;
}
template <class H, class ...T> void wr(H x, T... y) {
wr(x); wr(y...);
}
inline void Open(const string Name) {
#ifndef ONLINE_JUDGE
(void)!freopen((Name + ".in").c_str(), "r", stdin);
(void)!freopen((Name + ".out").c_str(), "w", stdout);
#endif
}
struct point {
int x, y;
void re() {
cin >> x >> y;
}
point operator + (const point& b) const {
return point{x + b.x, y + b.y};
}
point operator - (const point& b) const {
return point{x - b.x, y - b.y};
}
ll operator * (const point& b) const {
return (ll)x * b.y - (ll)y * b.x;
}
bool operator < (const point& b) const {
if(x != b.x)
return x < b.x;
return y < b.y;
}
bool operator > (const point& b) const {
if(x != b.x)
return x > b.x;
return y > b.y;
}
void operator += (const point& b) {
x += b.x;
y += b.y;
}
void operator -= (const point &b) {
x -= b.x;
y -= b.y;
}
void operator *= (const int k) {
x *= k;
y *= k;
}
ll cross(const point& b, const point& c) const {
return (b - *this) * (c - *this);
}
ll dist(const point &b) {
return (ll)(x - b.x) * (x - b.x) + (ll)(y - b.y) * (y - b.y);
}
};
void solve() {
int n; re(n);
vt <point> x(n), y(n), v(n + 1);
for(int i = 0;i < n;i++)
x[i].re();
sort(all(x));
for(int i = 0;i < n;i++)
y[i] = point{x[i].y, x[i].x};
auto go = [&](auto&& go, int l, int r, vt <point>& x, vt <point>& y) -> ll {
if(l >= r - 1)
return 4e18;
else if(r - l == 2) {
if(y[l] > y[l + 1]) {
swap(y[l], y[l + 1]);
}
return x[l].dist(x[l + 1]);
}
int m = (l + r) / 2;
ll best = min(go(go, l, m, x, y), go(go, m, r, x, y));
sort(y.begin() + l, y.begin() + r);
int v_size = 0;
for(int i = l;i < r;i++)
if(abs(y[i].y - x[m].x) <= best) {
v[v_size++] = y[i];
}
for(int i = 0;i < v_size - 1;i++)
for(int j = i + 1;j < v_size && j - i < 8;j++)
best = min(best, v[i].dist(v[j]));
return best;
};
cout << fixed << setprecision(6);
wr((ld)sqrt(go(go, 0, sz(x), x, y)));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Open("cmap");
int t = 1;
for(;t;t--) {
solve();
}
return 0;
}