Pagini recente » Cod sursa (job #2433039) | Cod sursa (job #1433435) | Cod sursa (job #377534) | Cod sursa (job #1370337) | Cod sursa (job #1662820)
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAX = 100001;
const long long INF = 2000000000000000000LL;
struct puncte
{
int x, y;
}v[MAX], aux[MAX];
long long dist(puncte a, puncte b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
long long modul(long long a)
{
if(a < 0)
return -a;
return a;
}
bool cmpx(puncte a, puncte b)
{
return a.x < b.x;
}
long long compute(int st, int dr, long long d)
{
int nr, m = (st + dr) / 2, i, j, k, lim;
puncte mij = v[m];
i = k = st;
j = m + 1;
while (i <= m && j <= dr)
if (v[i].y <= v[j].y)
aux[k++] = v[i++];
else
aux[k++] = v[j++];
while (i <= m)
aux[k++] = v[i++];
while (j <= dr)
aux[k++] = v[j++];
nr = 0;
for (i = st; i <= dr; i++)
{
v[i] = aux[i];
if (modul(v[i].x - mij.x) <= d)
aux[nr++] = aux[i];
}
for (i = 0; i + 1 < nr; i++)
{
lim = i + 8;
if (lim > nr)
lim = nr;
for (j = i + 1; j < lim; j++)
d = min(d, dist(aux[i], aux[j]));
}
return d;
}
long long divide(int left, int right)
{
if(left == right)
return INF;
int mid = (right + left)/2;
long long d1 = divide(left, mid);
long long d2 = divide(mid + 1, right);
long long delta = min(d1, d2);
return compute(left, right, delta);
}
int main()
{
FILE *fin, *fout;
fin = fopen("cmap.in", "r");
fout = fopen("cmap.out", "w");
int n;
fscanf(fin, "%d", &n);
for(int i = 0; i < n; i++)
fscanf(fin, "%d %d", &v[i].x, &v[i].y);
sort(v, v + n, cmpx);
fprintf(fout, "%.6f", sqrt(divide(0, n - 1)));
return 0;
}