Pagini recente » Cod sursa (job #1759601) | Cod sursa (job #3164148) | Cod sursa (job #1378508) | Cod sursa (job #2583217) | Cod sursa (job #3148164)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
const long long INF = 4e18;
vector < pair <long long, long long> > v(NMAX), x, y;
long long dist(const pair <long long, long long>& a, const pair <long long, long long>& b) {
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
long long sl(int st, int dr, vector < pair <long long, long long> >& x, vector < pair <long long, long long> >& y) {
if (st >= dr - 1)
return INF;
else if (dr - st == 2) {
if (y[st] > y[st + 1])
swap(y[st], y[st + 1]);
return dist(x[st], x[st + 1]);
}
int md = (st + dr) / 2;
long long mn = min(sl(st, md, x, y), sl(md, dr, x, y));
merge(y.begin() + st, y.begin() + md, y.begin() + md, y.begin() + dr, v.begin());
copy(v.begin(), v.begin() + (dr - st), y.begin() + st);
int cnt = 0;
for (int i = st;i < dr;i++)
if (abs(y[i].second - x[md].first) <= mn)
v[cnt++] = y[i];
for (int i = 0;i < cnt - 1;i++) {
for (int j = i + 1;j < cnt && j - i < 8;j++)
mn = min(mn, dist(v[i], v[j]));
}
return mn;
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
fin >> n;
x.resize(n), y.resize(n);
for (int i = 0;i < n;i++)
fin >> x[i].first >> x[i].second;
sort(x.begin(), x.end());
for (int i = 0;i < n;i++)
y[i] = make_pair(x[i].second, x[i].first);
fout << fixed << setprecision(6) << sqrt(sl(0, n, x, y)) << '\n';
return 0;
}