Pagini recente » Cod sursa (job #1608278) | Cod sursa (job #1393953) | Cod sursa (job #2460150) | Cod sursa (job #1670153) | Cod sursa (job #3225800)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int NMAX = 1e5;
int n;
pair<int, int> a[NMAX + 1];
ll dist(pair<int, int> a, pair<int, int> b) {
return 1LL * (a.first - b.first) * (a.first - b.first) + 1LL * (a.second - b.second) * (a.second - b.second);
}
bool cmpX(const pair<int, int> & a, const pair<int, int> & b) {
return a.first < b.first;
}
bool cmpY(const pair<int, int> & a, const pair<int, int> & b) {
return a.second < b.second;
}
ll ans;
void go(int st, int dr) {
if (st >= dr)
return;
if (dr == st + 1) {
ans = min(ans, dist(a[st], a[dr]));
return;
}
int mij = (st + dr) / 2;
go(st, mij);
go(mij + 1, dr);
vector<pair<int, int>> v;
for (int i = st; i <= dr; i++)
if (1LL * (a[i].first - a[mij].first) * (a[i].first - a[mij].first) < ans)
v.push_back(a[i]);
sort(v.begin(), v.end(), cmpY);
for (int i = 0; i < v.size(); i++) {
for (int j = i + 1; j < v.size(); j++) {
if (1LL * (v[j].second - v[i].second) * (v[j].second - v[i].second) >= ans)
break;
ans = min(ans, dist(v[i], v[j]));
}
}
}
void solve() {
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].first >> a[i].second;
sort(a + 1, a + n + 1, cmpX);
ans = dist(a[1], a[2]);
go(1, n);
ld Ans = (ld)sqrt((ld)ans);
fout << fixed << setprecision(6) << Ans << '\n';
}
signed main() {
solve();
return 0;
}