练练手可以,不会就看算法导论吧。。
1 const int N = 100010;
2
3 struct point_t {
4 double x, y;
5 }p[N], Y[N];
6
7 double sqr(double x) { return x * x;}
8 bool cmp1(const point_t &a, const point_t &b)
9 {
10 if (a.x != b.x) {
11 return a.x < b.x;
12 }
13 return a.y < b.y;
14 }
15
16 bool cmp2(const point_t &a,const point_t &b)
17 {
18 if (a.y != b.y) {
19 return a.y < b.y;
20 }
21 return a.x < b.x;
22 }
23
24 const double inf = 1e100;
25 double dist(point_t a,point_t b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
26 int top;
27
28 double divide(int beg, int end)
29 {
30 double ans = inf;
31 int i,j;
32 if (end < beg + 3) {
33 for (i = beg;i <= end;i++) {
34 for (j = i + 1;j <= end;j++) {
35 ckmin(ans, dist(p[i], p[j]));
36 }
37 }
38 return ans;
39 }
40 int mid = (beg + end) >> 1, cnt;
41 ckmin(ans, divide(beg, mid));
42 ckmin(ans, divide(mid + 1, end));
43 for (i = beg, top = 0;i <= end;i++) {
44 if (fabs(p[i].x - p[mid].x) < ans) {
45 Y[top++] = p[i];
46 }
47 }
48 sort(Y, Y + top, cmp2);
49 for (i = 0;i < top;i++) {
50 for (cnt = 0,j = i + 1;j < top && cnt < 7;cnt++, j++) {
51 ckmin(ans, dist(Y[i], Y[j]));
52 }
53 }
54 return ans;
55 }
56
57 int n;
58 void proc()
59 {
60 int i,j,k;
61 sort(p, p + n, cmp1);
62 double ans = divide(0, n - 1);
63 printf("%.2f\n", ans/2.0);
64 }
65
66 int main()
67 {
68 int i,j,k;
69 while (scanf("%d", &n) == 1 && n) {
70 for (i = 0;i < n;i++) {
71 scanf("%lf %lf", &p[i].x, &p[i].y);
72 }
73 proc();
74 }
75 return 0;
76 }
77