平面最近点对（分治）

题目描述

给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的

输入输出格式

输入格式：

第一行：n；2≤n≤200000

接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。

输出格式：

仅一行，一个实数，表示最短距离，精确到小数点后面4位。

 1 //分治基础题
 2 #include<cmath>
 3 #include<vector>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<algorithm>
 7 using namespace std;
 8 int n,m,q,cnt;
 9 struct node{
10     int x;
11     int y;
12 }poi[200005],tmp[200005];
13 int cmp1(node a,node b){
14     if(a.x==b.x){
15         return a.y<a.y;
16     }
17     return a.x<b.x;
18 }
19 int cmp2(node a,node b){
20     return  a.y<b.y;
21 }
22 double cal(node a,node b){
23     long long x=1ll*abs(a.x-b.x)*abs(a.x-b.x);
24     long long y=1ll*abs(a.y-b.y)*abs(a.y-b.y);
25     return sqrt(x+y);
26 }
27 double solve(int l,int r){
28     double mn=0x3f3f3f3f;
29     if(l==r){
30         return mn;
31     }
32     if(l+1==r){
33         return cal(poi[l],poi[r]);
34     }
35     int mid=(l+r)>>1;
36     int tp=0;
37     double mnl=solve(l,mid);
38     double mnr=solve(mid+1,r);
39     mn=min(mnl,mnr);
40     for(int i=l;i<=r;i++){
41         if(abs(poi[i].x-poi[mid].x)<=mn)tmp[++tp]=poi[i];
42     }
43     sort(tmp+1,tmp+tp+1,cmp2);
44     for(int i=1;i<=tp;i++){
45         for(int j=1;j<=tp;j++){
46             if(i==j)continue;
47             if(abs(tmp[i].y-tmp[j].y)>mn)continue;
48             mn=min(mn,cal(tmp[i],tmp[j]));
49         }
50     }
51     return mn;
52 }
53 int main(){
54     scanf("%d",&n);
55     for(int i=1;i<=n;i++){
56         scanf("%d%d",&poi[i].x,&poi[i].y);
57     }
58     sort(poi+1,poi+n+1,cmp1);
59     double ans=solve(1,n);
60     printf("%.4lf",ans);
61     return 0;
62 }