Pagini recente » Cod sursa (job #2294099) | Cod sursa (job #2328497) | Cod sursa (job #512467) | Cod sursa (job #1813837) | Cod sursa (job #523217)
Cod sursa(job #523217)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
const int maxn = 100002;
typedef long long ll;
const ll inf = 3e18;
ifstream f("cmap.in");
ofstream g("cmap.out");
pair<int, int> a[maxn], b[maxn], aux[maxn];
int i, j, n;
ll dis(pair<int, int> a, pair<int, int> b)
{
return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}
ll get(int begin, int end)
{
if (begin == end)
return inf;
if (end - begin == 1)
{
if (b[end] < b[begin]) swap(b[begin], b[end]);
return dis(b[begin], b[end]);
}
int mid = (begin + end) / 2;
ll ans = min( get(begin, mid), get(mid + 1, end) );
merge(b + begin, b + mid + 1, b + mid + 1, b + end + 1, aux); //interclasare
copy(aux, aux + (end - begin + 1), b + begin);
int k = 0;
for (int i = begin; i <= end; ++i)
if ( abs(b[i].y - a[mid].x) <= ans)
aux[k++] = b[i];
for (int i = 0; i < k; ++i)
for (int j = i + 1; j < k && j <= i + 8; ++j)
ans = min(ans, dis(aux[i], aux[j]));
return ans;
}
int main()
{
f >> n;
for (i = 1; i <= n; ++i) f >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1);
for (i = 1; i <= n; ++i)
b[i] = make_pair(a[i].y, a[i].x);
g.setf(ios::fixed, ios::floatfield);
g.precision(6);
g << sqrt( get(1, n) ) << "\n";
}