1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
inline int sign(const double x)
{
static const double EPS = 1e-8;
if (x > EPS) return 1;
return x < -EPS ? -1 : 0;
}
inline double sqr(const double x) { return x*x; }
const int MAXN = 100000;
struct Point
{
double x, y;
Point() { }
Point(const double a, const double b):x(a), y(b) { }
};
inline bool cmpx(const Point& lhs, const Point& rhs) { return sign(lhs.x-rhs.x) < 0; }
inline bool cmpy(const Point& lhs, const Point& rhs) { return sign(lhs.y-rhs.y) < 0; }
inline double dist(const Point& a, const Point& b) { return sqr(a.x-b.x)+sqr(a.y-b.y); }
int n;
Point a[MAXN];
double solve(const int lef, const int rig)
{
static Point p[MAXN];
if (lef == rig) return 1e10;
const int mid = (lef+rig)/2;
double d = std::min(solve(lef, mid), solve(mid+1, rig));
int cnt = 0;
for (int i = mid; i >= lef && sign(a[mid].x-a[i].x-d) <= 0; --i) p[cnt++] = a[i];
for (int i = mid+1; i <= rig &&sign(a[i].x-a[mid].x-d) <= 0; ++i) p[cnt++] = a[i];
std::sort(p, p+cnt, cmpy);
for (int j = 0; j < cnt; ++j)
for (int k = j+1; k < cnt && k < j+7; ++k)
{
if (sign(p[k].y-p[j].y-d) > 0) break;
d = std::min(d, dist(p[j], p[k]));
}
return d;
}
int main()
{
while (scanf("%d", &n) != EOF && n)
{
for (int i = 0; i < n; ++i)
scanf("%lf%lf", &a[i].x, &a[i].y);
std::sort(a, a+n, cmpx);
printf("%.2f\n", std::sqrt(solve(0, n-1)) / 2.0);
}
}
|
