Pagini recente » Cod sursa (job #1218801) | Cod sursa (job #2302185) | Cod sursa (job #1115300) | Cod sursa (job #900200) | Cod sursa (job #1026964)
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <fstream>
using namespace std;
struct punct { int x; int y;} v[100002];
double minim(double x, double y)
{
if (x > y )
return y;
return x;
}
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;
min = minim( min, dei(st, m));
min = minim(min, dei(m + 1, dr));
punct tmp[10100];
int i, j, cnt = 0, contor;
for (i = m; i >= st; i--)
if (v[m].x - v[i].x <= min)
tmp[++cnt] = v[i];
for (i = m + 1; i <= dr; i++)
if (v[i].x - v[m].x <= min)
tmp[++cnt] = v[i];
sort(tmp + 1, tmp + cnt + 1, cmpy);
for (i = 1; i <= cnt; i++)
for (j = i + 1, contor = 1; j <= cnt && contor <= 6; ++j, ++contor)
min = minim(min, dist(tmp[i], tmp[j]));
return min;
}
int main() {
ifstream fin("cmap.in");
ofstream fout("cmap.out");
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);
fout<<dist;
return 0;
}