hdu 1007 Quoit Design (Nearest Point Pair)

http://acm.hdu.edu.cn/showproblem.php?pid=1007

　　最近点对。

　　做法是先对所有点先按x再按y排序，然后进行分治搜索最近点对。对于每个区间，如果点数小于3，就直接暴力搜索最近点，否则对其进行分治。分治出来的两个区间，我们要挑选出与中点距离小于已找到的最近距离的所有点，然后对他们进行暴力枚举最近距离。根据《算法导论》证明的，合并两个区间之后，被挑选出来的点不会超过6个，于是可以得到总的时间复杂度是O(nlogn)。

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <cmath>
 6 
 7 using namespace std;
 8 
 9 const int N = 111111;
10 const double FINF = 1e100;
11 
12 template <class T> T sqr(T x) { return x * x;}
13 struct Point {
14     double x, y;
15     Point() {}
16     Point(int x, int y) : x(x), y(y) {}
17     bool operator < (Point a) const {
18         return x < a.x || x == a.x && y < a.y;
19     }
20     Point operator + (Point a) {
21         return Point(x + a.x, y + a.y);
22     }
23 } p[N];
24 
25 bool cmpY(int x, int y) { return p[x].y < p[y].y;}
26 inline double dist(Point x, Point y) { return sqrt(sqr(x.x - y.x) + sqr(x.y - y.y));}
27 
28 #define lson l, m
29 #define rson m + 1, r
30 
31 int arr[N];
32 
33 double closest(int l, int r) {
34     if (l >= r) return FINF;
35     if (l + 1 == r) return dist(p[l], p[r]);
36     int m = l + r >> 1;
37     double cd = min(closest(lson), closest(rson));
38     int end = 0;
39     for (int i = l; i <= r; i++) {
40         if (dist(p[i], p[m]) <= cd) {
41             arr[end++] = i;
42         }
43     }
44     sort(arr, arr + end, cmpY);
45     for (int i = 0; i < end; i++) {
46         for (int j = i + 1; j < end; j++) {
47             cd = min(cd, dist(p[arr[i]], p[arr[j]]));
48         }
49     }
50     return cd;
51 }
52 
53 int main() {
54 //    freopen("in", "r", stdin);
55     int n;
56     while (~scanf("%d", &n) && n) {
57         for (int i = 0; i < n; i++) {
58             scanf("%lf%lf", &p[i].x, &p[i].y);
59         }
60         sort(p, p + n);
61         printf("%.2f\n", closest(0, n - 1) / 2.0);
62     }
63     return 0;
64 }

View Code

UPD：

　　之前的代码估计是水过了，更新一下代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cmath>
 6 
 7 using namespace std;
 8 
 9 template<class T> T sqr(T x) { return x * x;}
10 typedef pair<double, double> Point;
11 #define x first
12 #define y second
13 inline double dist(Point a, Point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
14 inline bool cmpx(Point a, Point b) { return a.x < b.x;}
15 inline bool cmpy(Point a, Point b) { return a.y < b.y;}
16 const int N = 111111;
17 const double FINF = 1e100;
18 
19 #define lson l, m
20 #define rson m + 1, r
21 Point pt[N], tmp[N];
22 
23 double npp(int l, int r) {
24     if (r - l <= 3) {
25         double ret = FINF;
26         for (int i = l; i < r; i++) {
27             for (int j = i + 1; j <= r; j++) {
28                 ret = min(ret, dist(pt[i], pt[j]));
29             }
30         }
31         return ret;
32     }
33     int m = l + r >> 1;
34     Point mid = pt[m];
35     double md = min(npp(lson), npp(rson));
36     int tt = 0;
37     for (int i = l; i <= r; i++) if (fabs(pt[i].x - mid.x) <= md) tmp[tt++] = pt[i];
38     sort(tmp, tmp + tt, cmpy);
39     for (int i = 0; i < tt; i++) {
40         int j = i + 1;
41         while (j < tt) {
42             if (tmp[j].y - tmp[i].y > md) break;
43             md = min(md, dist(tmp[i], tmp[j]));
44             j++;
45         }
46     }
47     return md;
48 }
49 
50 int main() {
51     //freopen("in", "r", stdin);
52     int n;
53     while (~scanf("%d", &n) && n) {
54         for (int i = 0; i < n; i++) scanf("%lf%lf", &pt[i].x, &pt[i].y);
55         sort(pt, pt + n, cmpx);
56         printf("%.2f\n", npp(0, n - 1) / 2);
57     }
58     return 0;
59 }

View Code

——written by Lyon