Pagini recente » Cod sursa (job #2207406) | Cod sursa (job #2117772) | Cod sursa (job #1928134) | Cod sursa (job #2196501) | Cod sursa (job #2089148)
#include <bits/stdc++.h>
using namespace std;
#define Punct pair<long long, long long>
#define X first
#define Y second
#define NMAX 100005
long long sqr(long long x) { return x * x; }
Punct px[NMAX];
Punct py[NMAX];
Punct aux[NMAX];
int n;
bool dupaX(Punct a, Punct b) {
if (a.X == b.X)
return a.Y < b.Y;
return a.X < b.X;
}
bool dupaY(Punct a, Punct b) {
if (a.Y == b.Y)
return a.X < b.X;
return a.Y < b.Y;
}
void citire() {
scanf("%d ", &n);
for (int i = 0; i < n; i++) {
long long x, y;
scanf("%lld %lld ", &x, &y);
px[i] = { x, y };
py[i] = { x, y };
}
sort(px, px + n, dupaX);
sort(py, py + n, dupaY);
}
long long dist(Punct a, Punct b) {
return sqr(a.X - b.X) + sqr(a.Y - b.Y);
}
long long divide(int st, int dr) {
if (st == dr)
return 1LL<<60;
if (abs(st - dr) == 1)
return dist(py[st], py[dr]);
int mij = (st + dr) / 2;
long long res = min(divide(st, mij), divide(mij + 1, dr));
merge(py + st, py + mij + 1, py + mij + 1, py + dr + 1, aux);
copy(aux, aux + (dr - st + 1), py + st);
int k = 0;
for (int i = st; i <= dr; i++) {
if (abs(px[mij].X - py[i].X) <= res && i != mij)
aux[k++] = py[i];
}
for (int i = 0; i < k; i++)
for (int j = i + 1; j < k && j <= i + 6; j++)
res = min(res, dist(aux[i], aux[j]));
return res;
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
citire();
printf("%lf\n", sqrt(divide(0, n - 1)));
return 0;
}