Pagini recente » Cod sursa (job #185470) | Cod sursa (job #2482721) | Cod sursa (job #734640) | Cod sursa (job #164299) | Cod sursa (job #2738224)
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int, int>
#define ll long long
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const int N = 1e6 + 1;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
pii p[100002], cox[100002];
ll dist (pii a, pii b) {
return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y);
}
vector<pii>v[(1 << 18) + 2];
pii a[100002];
int n, x, y;
ll divide (int nod, int st, int dr) {
if (dr - st + 1 <= 3) {
ll ans = INF;
for (int j = st; j <= dr; j++) {
v[nod].push_back(cox[j]);
for (int k = j + 1; k <= dr; k++)
ans = min(ans, dist(p[j], p[k]));
}
sort(v[nod].begin(), v[nod].end());
return ans;
}
int mij = (st + dr) / 2;
ll best = min(divide(2 * nod, st, mij), divide(2 * nod + 1, mij + 1, dr));
v[nod].resize(dr - st + 1);
merge(v[2 * nod].begin(), v[2 * nod].end(), v[2 * nod + 1].begin(), v[2 * nod + 1].end(), v[nod].begin());
v[2 * nod].clear();
v[2 * nod + 1].clear();
int nr = 0;
for (int i = 0; i < v[nod].size(); i++)
if (1ll * (v[nod][i].x - p[mij].x) * (v[nod][i].x - p[mij].x) < best)
a[++nr] = v[nod][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()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> p[i].x >> p[i].y;
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++)
cox[i] = {p[i].second, p[i].first};
fout << fixed << setprecision(10) << sqrt((double)divide(1, 1, n)) << "\n";
return 0;
}