算法分析实践——最近对问题

问题：

对

解析：

对于每个点集，分成l和r两个点集。

假设最近点对P，Q。

对于P，Q所属的点集共有三种情况：

1.P，Q同属于l点集

2.P，Q同属于r点集

3.P，Q属于不同点集

三者取最小值，既是我们需要求的最小值点。

分治思想，对于每个点堆，分成l和r两个点集，分别求每个点集中点的最近对。共有四种情况：

1.n == 1 ，只有一个点，无法构成最近对，返回inf

2.n == 2 ，只有一对，暴力计算，返回最小点距

3.n == 3，暴力计算，返回最小点距

4.n > 3 ,将问题分为更小的两个集合，递归返回最小点距

设计（核心代码）：

 1 int cmp1(point& a, point& b)
 2 {
 3     return a.x < b.x;
 4 }
 5 int cmp2(point& a, point& b)
 6 {
 7     return a.y < b.y;
 8 }
 9 
10 double get_dis(point p1, point p2)
11 {
12     return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
13 }
14 
15 int EffcientClosestPair(point p[], int l, int r)
16 {
17     if (r == l) return inf;
18     if (r - l == 1)
19     {
20         return get_dis(p[l], p[r]);
21     }
22     if(r - l == 2)
23     {
24         double d1 = get_dis(p[l], p[r]);
25         double d2 = get_dis(p[l], p[l + 1]);
26         double d3 = get_dis(p[l + 1], p[r]);
27         return min(d1, min(d2, d3));
28     }
29     int mid = (r + l) >> 1;
30     double d = min(EffcientClosestPair(p, l, mid) , EffcientClosestPair(p, mid + 1, r));
31     int ql = l , qr = r;
32     while (p[ql].x < p[mid].x - d && ql <= r) ++l;
33     while (p[qr].x > p[mid].x + d && qr >= l) --r;
34     for (int i = l; i <= r; ++i)
35     {
36         tmp[i] = p[i];
37     }
38     sort(tmp + l, tmp + r + 1, cmp2);
39     for (int i = l; i <= r; ++i)
40     {
41         for (int j = l + 1; j <= r; ++j)
42         {
43             if (tmp[j].y - tmp[i].y >= d)
44                 break;
45             else
46                 d = min(d, get_dis(tmp[i], tmp[j]));
47         }
48     }
49     return d;
50 
51 }

Github：

https://github.com/BambooCertain/Algorithm.git

完整代码：

 1 #include<cstdio>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<vector>
 7 #include<queue>
 8 #include<set>
 9 #include<map>
10 #include<cctype>
11 #define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
12 #define mem(a,x) memset(a,x,sizeof(a))
13 #define lson rt<<1,l,mid
14 #define rson rt<<1|1,mid + 1,r
15 #define P pair<int,int>
16 #define ull unsigned long long
17 using namespace std;
18 typedef long long ll;
19 const int maxn = 5e5 + 10;
20 const ll mod = 998244353;
21 const int inf = 0x3f3f3f3f;
22 const long long INF = 0x3f3f3f3f3f3f3f3f;
23 const double eps = 1e-7;
24 
25 
26 
27 
28 int n, m, k;
29 int arr[maxn], pos[maxn], res = 0, cnt[maxn] = {0}, ans2[maxn] , ans1[maxn];
30 
31 struct point {
32     double x, y;
33 }p[maxn],tmp[maxn];
34 
35 
36 int cmp1(point& a, point& b)
37 {
38     return a.x < b.x;
39 }
40 int cmp2(point& a, point& b)
41 {
42     return a.y < b.y;
43 }
44 
45 double get_dis(point p1, point p2)
46 {
47     return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
48 }
49 
50 int EffcientClosestPair(point p[], int l, int r)
51 {
52     if (r == l) return inf;
53     if (r - l == 1)
54     {
55         return get_dis(p[l], p[r]);
56     }
57     if(r - l == 2)
58     {
59         double d1 = get_dis(p[l], p[r]);
60         double d2 = get_dis(p[l], p[l + 1]);
61         double d3 = get_dis(p[l + 1], p[r]);
62         return min(d1, min(d2, d3));
63     }
64     int mid = (r + l) >> 1;
65     double d = min(EffcientClosestPair(p, l, mid) , EffcientClosestPair(p, mid + 1, r));
66     int ql = l , qr = r;
67     while (p[ql].x < p[mid].x - d && ql <= r) ++l;
68     while (p[qr].x > p[mid].x + d && qr >= l) --r;
69     for (int i = l; i <= r; ++i)
70     {
71         tmp[i] = p[i];
72     }
73     sort(tmp + l, tmp + r + 1, cmp2);
74     for (int i = l; i <= r; ++i)
75     {
76         for (int j = l + 1; j <= r; ++j)
77         {
78             if (tmp[j].y - tmp[i].y >= d)
79                 break;
80             else
81                 d = min(d, get_dis(tmp[i], tmp[j]));
82         }
83     }
84     return d;
85 
86 }
87 
88 int main()
89 {
90     scanf("%d", &n);
91     for (int i = 1; i <= n; ++i)
92     {
93         scanf("%lf %lf", &p[i].x, &p[i].y);
94     }
95     sort(p + 1, p + 1 + n, cmp1);
96     cout << EffcientClosestPair(p, 1, n) << endl;
97     return 0;
98 }

完整代码