Pagini recente » Cod sursa (job #2199069) | Cod sursa (job #2316263) | Cod sursa (job #2055545) | Cod sursa (job #362213) | Cod sursa (job #2495151)
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
FILE* in = fopen ("cmap.in", "r");
FILE* out = fopen ("cmap.out", "w");
vector < pair <uint64_t, uint64_t> > v, w;
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) {return dist(v[st], v[dr - 1]);}
if (dr - st == 3) {return max (dist(v[st], v[st+1]), max(dist(v[st], v[st+2]), dist(v[st+1], v[st+2])));}
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]) {w[nr++] = v[i++];}
else {w[nr++] = v[j++];}
}
while (i < mid) {w[nr++] = v[i++];}
while (j < dr) {w[nr++] = v[j++];}
nr = 0;
mid = w[mid].first;
for (i = st; i < dr; ++i)
{
if (abs(v[i].second - mid) <= ret)
{
w[nr++] = v[i];
}
}
for (i = 0; i < nr - 1; ++i)
{
for (j = i + 1; j < nr && j - i < 8; ++j)
{
ret = min(ret, dist(w[i], w[j]));
}
}
return ret;
}
int main(void)
{
int n;
fscanf (in, "%d", &n);
v.resize(n);
w.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());
fprintf (out, "%.6f", sqrt(rec(0, n)));
fclose (out);
return 0;
}