Pagini recente » Cod sursa (job #1481233) | Cod sursa (job #784337) | Cod sursa (job #1924212) | Cod sursa (job #2264604) | Cod sursa (job #1027016)
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <fstream>
using namespace std;
struct punct {long long x, y;} v[100002];
void minim(double &x, double y)
{
if (x > y)
x = y;
}
bool cmpx(punct a, punct b)
{
return a.x < b.x;
}
bool cmpy(punct a, punct b)
{
return a.y < b.y;
}
double dist(punct a, punct b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double dei(int st, int dr)
{
if (st >= dr)
return 1 << 30;
if (st + 1 == dr)
return dist(v[st], v[dr]);
int m = (st + dr) / 2;
double min = 1 << 30;
minim(min, dei(st, m));
minim(min, dei(m + 1, dr));
punct u[10100];
int i, j, cnt = 0, contor;
for (i = st; i <= dr; ++i)
if (abs(v[m].x - v[i].x) <= min)
u[++cnt] = v[i];
sort(u + 1, u + cnt + 1, cmpy);
for (i = 1; i <= cnt; ++i)
for (j = i + 1, contor = 1; j <= cnt && contor <= 6; ++j, ++contor)
minim(min, dist(u[i], u[j]));
return min;
}
int main()
{
ifstream fin("cmap.in");
freopen("cmap.out", "w", stdout);
int n;
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> v[i].x>>v[i].y;
sort(v + 1, v + n + 1, cmpx);
double dist = dei(1, n);
printf("%.6lf\n", dist);
return 0;
}