Pagini recente » Cod sursa (job #2312942) | Cod sursa (job #531533) | Cod sursa (job #2630032) | Cod sursa (job #1635677) | Cod sursa (job #1191025)
#include <cmath>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
const double INF = 1e10;
int N;
vector<pair<int, int> > A;
pair<int, int> B[100002];
int sz;
inline double q_dist(const pair<int, int>& p1, const pair<int, int>& p2)
{
return 1.0 * (p1.first - p2.first) * (p1.first - p2.first) + 1.0 * (p1.second - p2.second) * (p1.second - p2.second);
}
double get_dist(int i1, int i2)
{
if (i1 == i2) return INF;
if (i1 + 1 == i2) return q_dist(A[i1], A[i2]);
int mid = (i1 + i2) / 2;
int xn = A[mid].first;
double d1 = get_dist(i1, mid), d2 = get_dist(mid + 1, i2);
double dnow = min(d1, d2);
sz = 0;
for (int i = 0; i < int(A.size()); ++i)
if (A[i].first >= xn - dnow && A[i].first <= xn + dnow)
B[++sz] = make_pair(A[i].second, A[i].first);
sort(B + 1, B + sz + 1);
for (int i = 1; i <= sz; ++i)
for (int j = 1; i + j <= sz && j <= 7; ++j)
dnow = min(dnow, q_dist(B[i], B[i + j]));
return dnow;
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
fin >> N;
for (int i = 1; i <= N; ++i)
{
A.push_back(make_pair(0, 0));
fin >> A.back().first >> A.back().second;
}
sort(A.begin(), A.end());
fout << fixed << setprecision(8) << sqrt(get_dist(0, int(A.size()) - 1)) << '\n';
fin.close();
fout.close();
}