Pagini recente » Cod sursa (job #1873488) | Cod sursa (job #2668511) | Cod sursa (job #324933) | Cod sursa (job #1282908) | Cod sursa (job #1748977)
#include <bits/stdc++.h>
using ll = long long;
const ll INF = std::numeric_limits <ll>::max();
std::vector <std::pair <int, int> > x;
std::vector <std::pair <int, int> > y;
std::vector <std::pair <int, int> > temp(100000);
int n;
inline ll
dist(std::pair <int, int>& a,
std::pair <int, int>& b)
{
return ( (a.first - b.first) * (a.first - b.first) +
(a.second - b.second) * (a.second - b.second) );
}
ll
haida(int beg,
int end)
{
int mid;
ll min;
int i;
int index;
int j;
if (beg == end)
{
return INF;
}
if (beg == end - 1)
{
if (y[beg].first > y[end].first)
{
std::swap(y[beg],
y[end]);
return dist(y[beg],
y[end]);
}
}
mid = (beg + end) / 2;
min = std::min(haida(beg, mid),
haida(mid + 1, end));
std::merge(y.begin() + beg, y.begin() + mid + 1, y.begin() + mid + 1, y.begin() + end + 1, temp.begin());
std::copy(temp.begin(), temp.begin() + end - beg + 1, y.begin() + beg);
index = 0;
for (i = beg; i <= end; ++i)
{
if (abs(y[i].second - x[mid].first) <= min)
{
temp[index++] = y[i];
}
}
for (i = 0; i < index; ++i)
{
for (j = i + 1; (j < index) and (j - i < 8); ++j)
{
if (dist(y[i], y[j]) < min)
{
min = dist(y[i], y[j]);
}
}
}
return min;
}
int main()
{
std::ifstream mama("cmap.in");
std::ofstream tata("cmap.out");
mama >> n;
x.resize(n);
for (int i = 0; i < n; ++i)
{
mama >> x[i].first >> x[i].second;
}
std::sort(x.begin(),
x.end());
for (int i = 0; i < n; ++i)
{
y.push_back(std::make_pair(x[i].second, x[i].first));
}
tata << std::setprecision(15) << sqrt(haida(0, n - 1));
return 0;
}