Pagini recente » Statistici Andrei Cartof (Cartofen) | Statistici darius (dariussss) | Diferente pentru concursuri intre reviziile 62 si 63 | Istoria paginii utilizator/professionalacer | Cod sursa (job #1191036)
#include <cmath>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
const long long INF = (1LL << 60);
int N;
vector<pair<int, int> > A;
pair<int, int> B[100002], C[100002];
int sz;
inline long long q_dist(const pair<int, int>& p1, const pair<int, int>& p2)
{
return 1LL * (p1.first - p2.first) * (p1.first - p2.first) + 1LL * (p1.second - p2.second) * (p1.second - p2.second);
}
long long 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;
long long d1 = get_dist(i1, mid), d2 = get_dist(mid + 1, i2);
long long dnow = min(d1, d2);
merge(A.begin() + i1, A.begin() + mid + 1, A.begin() + mid + 1, A.begin() + i2 + 1, B);
sz = 0;
for (int i = 0; i < i2 - i1 + 1; ++i)
if (B[i].second >= xn - dnow && B[i].second <= xn + dnow)
C[++sz] = B[i];
for (int i = 1; i <= sz; ++i)
for (int j = 1; i + j <= sz && j <= 7; ++j)
dnow = min(dnow, q_dist(C[i], C[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());
for (int i = 0; i < int(A.size()); ++i)
swap(A[i].first, A[i].second);
fout << fixed << setprecision(8) << sqrt(1.0L * get_dist(0, int(A.size()) - 1)) << '\n';
fin.close();
fout.close();
}