Pagini recente » Cod sursa (job #2711772) | Cod sursa (job #823707) | Cod sursa (job #685030) | Cod sursa (job #638127) | Cod sursa (job #2499008)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define int long long
const int INF = 1e18;
vector <pair <int, int> > points;
int sq(int x)
{
return x * x;
}
int dist(pair <int, int> A, pair <int, int> B)
{
return (sq(A.first - B.first) + sq(A.second - B.second));
}
int solve(int l, int r)
{
if(r - l <= 3)
{
int res = INF;
for(int i = l; i < r; i++)
for(int j = i + 1; j <= r; j++)
res = min(res, dist(points[l], points[r]));
return res;
}
int mid = (l + r) / 2;
int d = min(solve(l, mid), solve(mid + 1, r));
vector <pair <int, int> > aux;
for(int i = l; i <= r; i++)
if(abs(points[mid].first - points[i].first) <= d)
aux.push_back({points[i].second, points[i].first});
sort(aux.begin(), aux.end());
for(int i = 0; i < aux.size(); i++)
for(int j = i + 1; j < aux.size() && j - i < 8; j++)
d = min(d, dist(aux[i], aux[j]));
return d;
}
main()
{
int n;
fin >> n;
for(int i = 1; i <= n; i++)
{
int x, y;
fin >> x >> y;
points.push_back({x, y});
}
sort(points.begin(), points.end());
fout << fixed << setprecision(7) << sqrt(1.0 * solve(0, n - 1)) << '\n';
}