题目描述

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

输入输出格式

输入格式：

 

第一行：n；2≤n≤200000

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

 

输出格式：

 

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

1 //分治基础题 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           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
          
           >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 }