Pagini recente » Cod sursa (job #2109231) | Cod sursa (job #1833068) | Cod sursa (job #2409972) | Cod sursa (job #1595247) | Cod sursa (job #2672380)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
int n;
vector<pair<int, int>> X, Y, v;
int dist(pair<int, int> a, pair<int, int> b)
{
return (a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second);
}
int solve(vector<pair<int, int>> X, vector<pair<int, int>> Y, int l, int r)
{
if(l == r - 1)
return dist(X[l], X[l + 1]);
if(l == r - 2)
return min(dist(X[l], X[l + 1]), dist(X[l + 1], X[l + 2]));
int mid = (l + r) / 2;
int best = min(solve(X, Y, l, mid), solve(X, Y, mid, r));
sort(Y.begin() + l, Y.begin() + r);
v.clear();
for(int i = l; i <= r; i++)
if(abs(Y[i].first - X[mid].first) < best)
v.emplace_back(Y[i].first, Y[i].second);
int len = v.size();
for(int i = 0; i < len; i++)
for(int j = i + 1; j < len && j - i < 8; j++)
best = min(best, dist(v[i], v[j]));
return best;
}
int main()
{
in >> n;
for(int i = 0; i < n; i++)
{
int x, y;
in >> x >> y;
X.emplace_back(x, y);
}
sort(X.begin(), X.end());
for(int i = 0; i < n; i++)
Y.emplace_back(X[i].second, X[i].first);
out << fixed << setprecision(6) << sqrt(solve(X, Y, 0, n - 1)) << '\n';
return 0;
}