Pagini recente » Cod sursa (job #1964663) | Cod sursa (job #315574) | Cod sursa (job #1370446) | Cod sursa (job #1619046) | Cod sursa (job #2503373)
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdint>
using namespace std;
FILE* in = fopen ("cmap.in", "r");
FILE* out = fopen ("cmap.out", "w");
vector < pair <uint64_t, uint64_t> > v, w, vv;
uint64_t dist (const pair <uint64_t, uint64_t>& a, const pair <uint64_t, uint64_t>& b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
uint64_t rec(int st, int dr)
{
if (dr - st <= 1) {return 0xffffff;}
if (dr - st == 2)
{
if (w[st] > w[dr-1]) {swap (w[st], w[dr-1]);}
return dist(v[st], v[dr - 1]);
}
int mid = (st + dr) / 2, i = st, j = mid, nr = st;
uint64_t ret = min(rec(st, mid), rec(mid, dr));
while (i < mid && j < dr)
{
if (w[i] < w[j]) {vv[nr++] = w[i++];}
else {vv[nr++] = w[j++];}
}
while (i < mid) {vv[nr++] = w[i++];}
while (j < dr) {vv[nr++] = w[j++];}
nr = 0;
for (i = st; i < dr; ++i)
{
if (abs(w[i].second - v[i].first) <= ret)
{
vv[nr++] = w[i];
}
}
for (i = 0; i < nr - 1; ++i)
{
for (j = i + 1; j < nr && j - i < 8; ++j)
{
ret = min(ret, dist(vv[i], vv[j]));
}
}
return ret;
}
int main(void)
{
int n;
fscanf (in, "%d", &n);
v.resize(n);
w.resize(n);
vv.resize(n);
for (int i = 0; i < n; ++i)
{
fscanf (in, "%I64d%I64d", &v[i].first, &v[i].second);
}
fclose (in);
sort(v.begin(), v.end());
for (int i = 0; i < n; ++i)
{
w[i] = make_pair (v[i].second, v[i].first);
}
fprintf (out, "%.6f", sqrt(rec(0, n)));
fclose (out);
return 0;
}