Smiling & Weeping

　　　　　　　　　　　---- 当上天赐给你荒野时，就意味着，他要你成为高飞的鹰

题目链接：P1257 平面上的最接近点对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目大意：找到平面上两个距离最近的点，我们首先想到的是暴力破解O(n*n),时间似乎有些长，那我们可以使用分治来解决问题。

Talk is cheap , show me the code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const double eps = 1e-8;
 4 const int N = 100010;
 5 const double INF = 1e20;
 6 int sgn(double x){
 7     if(fabs(x) < eps) return 0;
 8     return x < 0 ? -1 : 1;
 9 }
10 struct Point{ double x , y; };
11 double Distance(Point a, Point b){
12     return hypot(a.x-b.x , a.y-b.y);
13 }
14 bool cmpxy(Point a , Point b){
15     return sgn(a.x-b.x)<0 || (sgn(a.x-b.x)==0 && sgn(a.y-b.y)<0);
16 }
17 bool cmpy(Point a , Point b){return sgn(a.y-b.y) < 0; }
18 Point p[N] , tem_p[N];
19 double Closest_Pair(int left , int right){
20     double dis = INF;
21     if(left == right) return dis;           // 只剩一个点
22     if(left+1 == right) return Distance(p[left] , p[right]); // 只剩两个点
23     int mid = left+right>>1;
24     double d1 = Closest_Pair(left , mid);
25     double d2 = Closest_Pair(mid+1 , right);
26     dis = min(d1 , d2);
27     int k = 0;
28     for(int i = left; i <= right; i++){
29         if(fabs(p[mid].x-p[i].x) <= dis)
30             tem_p[k++] = p[i];
31     }
32     sort(tem_p,tem_p+k,cmpy);       // 按y坐标排序，用于剪枝，这里不能按x排序
33     for(int i = 0; i < k; i++)
34         for(int j = i+1; j < k; j++){
35             if(tem_p[j].y - tem_p[i].y >= dis) break;
36             dis = min(dis , Distance(tem_p[i] , tem_p[j]));
37         }
38     return dis;
39 }
40 int main()
41 {
42     int n;
43     scanf("%d",&n);
44     for(int i = 0; i < n; i++)
45         scanf("%lf%lf",&p[i].x,&p[i].y);
46         sort(p,p+n,cmpxy);
47         printf("%.4f\n",Closest_Pair(0,n-1));
48     return 0;
49 }