Pagini recente » Cod sursa (job #1941254) | Cod sursa (job #2289398) | Cod sursa (job #555722) | Cod sursa (job #2600405) | Cod sursa (job #2738233)
#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;
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++) {
for (int k = j + 1; k <= dr; k++)
ans = min(ans, dist(p[j], p[k]));
}
sort(cox + st, cox + dr +1);
return ans;
}
int mij = (st + dr) / 2;
ll best = min(divide(2 * nod, st, mij), divide(2 * nod + 1, mij + 1, dr));
v.resize(dr - st + 1);
merge(cox + st, cox + mij + 1, cox + mij + 2, cox + dr + 1, v.begin());
for (int i = 0; i < v.size(); i++)
cox[st + i] = v[i];
int nr = 0;
for (int i = st; i <= dr; i++)
if (1ll * (cox[i].y - p[mij].x) * (cox[i].y - p[mij].x) < best)
a[++nr] = cox[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;
}