Pagini recente » Cod sursa (job #2533313) | Cod sursa (job #2665359) | Cod sursa (job #2815166) | Cod sursa (job #2397438) | Cod sursa (job #2797253)
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
int n;
struct point {
ll x,y;
bool operator < (const point &a) {
if (x == a.x)
return y < a.y;
return x < a.x;
}
} p[100002], inv[100002], a[100002];
ll dist (point a, point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
vector<point>v;
ll divide (int st, int dr) {
if (dr - st + 1 <= 3) {
ll ans = INF;
for (int i = st; i <= dr; i++)
for (int j = i + 1; j <= dr; j++)
ans = min(ans, dist(p[i], p[j]));
return ans;
}
int mid = (st + dr) / 2;
ll best = min(divide(st, mid), divide(mid + 1, dr));
v.resize(dr - st + 1);
merge(inv + st, inv + mid + 1, inv + mid + 1, inv + dr + 1, v.begin());
for (int i = st; i <= dr; i++)
inv[i] = v[i - st];
int nr = 0;
for (int i = st; i <= dr; i++)
if ((inv[i].y - p[mid].x) * (inv[i].y - p[mid].x) < best)
a[++nr] = inv[i];
for (int i = 1; i <= nr; i++)
for (int j = max(1, i - 7); j <= i - 1; j++)
best = min(best, dist(a[i], a[j]));
return best;
}
int main()
{
// ios_base::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
fin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
fin >> p[i].x >> p[i].y;
}
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++)
inv[i] = {p[i].y, p[i].x};
fout << fixed << setprecision(10) << sqrt((long double)divide(1, n));
return 0;
}