Pagini recente » Cod sursa (job #1076579) | Cod sursa (job #1291287) | Cod sursa (job #1581314) | Cod sursa (job #145468) | Cod sursa (job #2870918)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("cmap.in");
ofstream out("cmap.out");
const int nmax = 1e5;
const long long inf = 1e18;
int n;
using Pii = pair<int, int>;
Pii a[nmax + 2];
long long dist(const Pii & p1, const Pii & p2){
return 1LL * (p1.first - p2.first) * (p1.first - p2.first) + 1LL * (p1.second - p2.second) * (p1.second - p2.second);
};
struct cmp{
bool operator()(const Pii & p1, const Pii & p2){
if(p1.second == p2.second)
return p1.first < p2.first;
else
return p1.second < p2.second;
}
};
Pii temp[nmax + 2];
long long divide(Pii * a, int n){
long long ans = inf;
if(n <= 3){
sort(a, a + n, cmp());
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
ans = min(ans, dist(a[i], a[j]));
return ans;
}
if(a[0].first == a[n - 1].first){
for(int i = 0; i < n - 1; i++)
ans = min(ans, dist(a[i], a[i + 1]));
return ans;
}
int m = n / 2, xx = a[m].first;
ans = min(ans, divide(a, m));
ans = min(ans, divide(a + m, n - m));
merge(a, a + m, a + m, a + n, temp, cmp());
memcpy(a, temp, n * 8);
m = 0;
for(int i = 0; i < n; i++)
if(abs(a[i].first - xx) <= ans)
temp[m++] = a[i];
for(int i = 0; i < m; i++)
for(int j = 1; j <= 7 && i + j < m; j++)
ans = min(ans, dist(a[i], a[i + j]));
return ans;
}
int main()
{
in >> n;
for(int i = 1; i <= n; i++)
in >> a[i].first >> a[i].second;
sort(a + 1, a + n + 1);
out << fixed << setprecision(6) << sqrt(divide(a + 1, n)) << "\n";
return 0;
}