Pagini recente » Cod sursa (job #2648203) | Cod sursa (job #2093157) | Cod sursa (job #1633570) | Cod sursa (job #3232307) | Cod sursa (job #2193047)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int MAXN = 1e5;
const long long INF = 2000LL * 1000 * 1000 * 2000 * 1000 * 1000;
typedef pair < int, int > Point;
Point xsort[MAXN], ysort[MAXN], aux[MAXN];
inline long long dsqr(Point A, Point B) {
return 1LL * (A.x - B.x) * (A.x - B.x) + 1LL * (A.y - B.y) * (A.y - B.y);
}
long long solve(int l, int r) {
if (l == r)
return INF;
if (l + 1 == r) {
if (ysort[l].y > ysort[r].y)
swap(ysort[l], ysort[r]);
return dsqr(ysort[l], ysort[r]);
}
int mid = (l + r) / 2, k = 0, i = l, j = mid + 1;
long long lim = min(solve(l, mid), solve(mid + 1, r));
while (i <= mid && j <= r)
if (ysort[i].y < ysort[j].y)
aux[k++] = ysort[i++];
else
aux[k++] = ysort[j++];
while (i <= mid)
aux[k++] = ysort[i++];
while (j <= r)
aux[k++] = ysort[j++];
for (int ind = l; ind <= r; ++ind)
ysort[ind] = aux[ind - l];
k = 0;
for (int ind = l; ind <= r; ++ind)
if (abs(ysort[ind].x - xsort[mid].x) <= lim)
aux[k++] = ysort[ind];
for (i = 0; i < k; ++i)
for (j = i + 1; j < min(k, i + 8); ++j)
lim = min(lim, dsqr(ysort[i], ysort[j]));
return lim;
}
int main()
{
int n;
ifstream fin("cmap.in");
fin >> n;
for (int i = 0; i < n; ++i) {
fin >> xsort[i].x >> xsort[i].y;
ysort[i] = xsort[i];
}
fin.close();
sort(xsort, xsort + n);
ofstream fout("cmap.out");
fout << setprecision(8) << fixed << sqrt(solve(0, n - 1)) << '\n';
fout.close();
return 0;
}