1.10HDU1007QuoitDesign

1 #include
2 #include
3 #include
4 using namespace std;
5 const int MAXN = 100100;
6 struct Point{
7 double x, y;
8 }x[MAXN];
9 int y[MAXN], z[MAXN];
10 bool cmpx(const Point& a, const Point& b)
11 { return a.x < b.x; }
12 bool cmpy(const int& a, const int &b)
13 { return x[a].y < x[b].y; }
14 inline double dis(Point a, Point b)
15 { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); }
16
17 void Merge(int z[], int y[], int l, int r, int m)
18 {
19 int i = l, j = m+1, k = l;
20 while(i <= m && j <= r)
21 if(x[z[i]].y <= x[z[j]].y) y[k++] = z[i++];
22 else y[k++] = z[j++];
23 while(i <= m) y[k++] = z[i++];
24 while(j <= r) y[k++] = z[j++];
25 }
26
27 double close(int y[], int z[], int l, int r)
28 {
29 if(l+1 == r)
30 return dis(x[l], x[r]);
31 if(l+2 == r)
32 return min(dis(x[l], x[l+1]), min(dis(x[l+1], x[r]), dis(x[l], x[r])));
33 int m = l+r>>1;
34 for(int i=l, j=m+1, k=l ; k<=r ; k++)
35 if(y[k] > m) z[j++] = y[k];
36 else z[i++] = y[k];
37 double res = min(close(z, y, l, m), close(z, y, m+1, r));
38 Merge(z, y, l, r, m);
39 int rt = l;
40 for(int i=l ; i<=r ; i++)
41 if(fabs(x[y[i]].x - x[y[m]].x) < res)
42 z[rt++] = y[i];
43 for(int i=l ; i)
44 for(int j=i+1 ; j)
45 {
46 if(x[z[j]].y - x[z[i]].y >= res) break;
47 res = min(res, dis(x[z[i]], x[z[j]]));
48 }
49 return res;
50 }
51
52 int main()
53 {
54 // freopen("input", "r", stdin);
55 int n;
56 while(scanf("%d", &n), n)
57 {
58 for(int i=0 ; i)
59 scanf("%lf %lf", &x[i].x, &x[i].y), y[i] = i;
60 sort(x, x+n, cmpx);
61 sort(y, y+n, cmpy);
62 printf("%.2lf\n", sqrt(close(y, z, 0, n-1))/2);
63 }
64 }

1 #include
2 #include <string.h>
3 #include
4 #include
5 const int MAXN = 100100;
6 struct Point{
7 double x, y;
8 }x[MAXN];
9 int y[MAXN], z[MAXN];
10 int cmpx(const void* a, const void* b)
11 { return ((Point*)a)->x - ((Point*)b)->x; }
12 int cmpy(const void* a, const void* b)
13 { return x[(*(int*)a)].y - x[(*(int*)b)].y; }
14 inline double min(double a, double b)
15 { return a a : b; }
16 inline double dis(Point a, Point b)
17 { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); }
18 void Merge(int z[], int y[], int l, int r, int m)
19 {
20 int i = l, j = m+1, k = l;
21 while(i <= m && j <= r)
22 if(x[z[i]].y <= x[z[j]].y) y[k++] = z[i++];
23 else y[k++] = z[j++];
24 while(i <= m) y[k++] = z[i++];
25 while(j <= r) y[k++] = z[j++];
26 }
27
28 double close(int y[], int z[], int l, int r)
29 {
30 if(l+1 == r)
31 return dis(x[l], x[r]);
32 if(l+2 == r)
33 return min(dis(x[l], x[l+1]), min(dis(x[l+1], x[r]), dis(x[l], x[r])));
34 int m = l+r>>1;
35 for(int i=l, j=m+1, k=l ; k<=r ; k++)
36 if(y[k] > m) z[j++] = y[k];
37 else z[i++] = y[k];
38 double res = min(close(z, y, l, m), close(z, y, m+1, r));
39 Merge(z, y, l, r, m);
40 int rt = l;
41 for(int i=l ; i<=r ; i++)
42 if(fabs(x[y[i]].x - x[y[m]].x) < res)
43 z[rt++] = y[i];
44 for(int i=l ; i)
45 for(int j=i+1 ; j)
46 {
47 if(x[z[j]].y - x[z[i]].y >= res) break;
48 res = min(res, dis(x[z[i]], x[z[j]]));
49 }
50 return res;
51 }
52
53 int main()
54 {
55 // freopen("input", "r", stdin);
56 int n;
57 while(scanf("%d", &n), n)
58 {
59 for(int i=0 ; i)
60 scanf("%lf %lf", &x[i].x, &x[i].y), y[i] = i;
61 qsort(x, n, sizeof(Point), cmpx);
62 qsort(y, n, sizeof(int), cmpy);
63 printf("%.2lf\n", sqrt(close(y, z, 0, n-1))/2);
64 }
65 }