分治——最近点对问题 hdu1007

时间:2022-12-17 13:37:18

问题描述

n个点在公共空间中,求出所有点对的欧几里得距离最小的点对。
分治——最近点对问题 hdu1007 

解法1: 很明显的,暴力解决是$O(N^2)$

 

解法2: 利用分治的思想,我们可以把算法优化到$O(nlogn*logn)$,甚至$O(nlogn)$

我们先对所有的点按照x坐标排序, 然后每次二分,很明显,这个二分很好写,难的是合并的操作。  即从左边A集合中选出一个点和右边集合B里面选出一个点。 

如果暴力的是去枚举左边和右边的点,还是$O(n^2)$。 

首先,我们先求出左边和右边集合的最小距离。 $d=min(dist_{left},dist_{right})$ 

 然后找出一个条左右集合的分界线。 如图所示

分治——最近点对问题 hdu1007

l就是左右集合的分界线。 

我们发现,我们只要在左边集合里面枚举横坐标在[mid-d,mid]和右边集合里面横坐标在[mid,mid+d]范围内的点进行配对就可以了。 因为明显的,另外的点的距离肯定更大。  

这样就大大缩小了我们枚举的范围,但是极端情况还是很大。 

 

 

1985年Preparata和Shamos在给出该问题的一个分治算法,指出对于左边的任意一个点,右边集合和他可以匹配成为最有解的最多只有6个点。

分治——最近点对问题 hdu1007

如图所示: 假如左边是p点,那么在分界线的右边和p点可以配对的点不会超过6个,即在那个δ×2δ的区间里面最多只有6个点。  

 

我们用反证法来证明。  

分治——最近点对问题 hdu1007

我们把δ×2δ这个矩阵按每$ \frac{2δ}{3}$来分,这样就有6个小矩形了我们可以知道每个小矩阵里面最多只有一个点,如果有两点,那么这两个点的距离一定要远一点,明显的,对角线的距离最短。 

此时对角线的距离就是$\sqrt{\frac{2δ}{3}×\frac{2δ}{3}+\frac{δ}{2}×\frac{δ}{2}}=\frac{\sqrt{5}}{6}δ$

此时说明右边原来就是小于d的点对(d和δ这里是一样的) ,明显与原来不符。 

所以最多只有6个点。(当然了,其实还能证明更少点)  

所以我们每次合并,对于左边的点最多只有6个匹配的方案。 考虑匹配方案的时候,需要对y进行排序,那么时间复杂度就变成了$O(n*logn*logn)$。  

但是其实我们可以做的更好,我们可以在分治的过程中,顺便做一个关于y坐标的归并排序,这样就不用每次对y进行sort了,时间也可以优化到$O(nlogn)$

下面是我的代码,还是写了2个$logn$的做法。 

分治——最近点对问题 hdu1007分治——最近点对问题 hdu1007
 1 #include<bits/stdc++.h>
 2 using namespace std; 
 3 int const N=100000+10;   
 4 struct node{
 5     double x,y;  
 6 }a[N];  
 7 int cmpx(int t1,int t2){
 8     return a[t1].x<a[t2].x;    
 9 }  
10 int cmpy(int t1,int t2){
11     return a[t1].y>a[t2].y;  
12 }
13 int n,t[N],c1[N],cnt1,c2[N],cnt2;    
14 double dist(int t1,int t2){
15     return sqrt( (a[t1].x-a[t2].x)*(a[t1].x-a[t2].x)+(a[t1].y-a[t2].y)*(a[t1].y-a[t2].y)); 
16 }
17 double calc(int l,int r,int mid,double d){
18     sort(c1+1,c1+cnt1+1,cmpy);  
19     sort(c2+1,c2+cnt2+1,cmpy);  
20     int k=1;    
21     double ret=d;  
22     for(int i=1;i<=cnt1;i++) {
23         while (k<=cnt2 && a[c2[k]].y-a[c1[i]].y>d) k++; 
24         for(int j=k;j<=cnt2;j++)   
25             if( a[c1[i]].y-a[c2[j]].y<d)   
26                 ret=min(ret,dist(c1[i],c2[j]));  
27             else break;  
28     }
29     return ret; 
30 } 
31         
32 double close_dist(int l,int r){
33     if(l==r) return 1e9;    
34     if(l+1==r) return dist(t[l],t[r]);
35     int mid=(l+r)/2; 
36     double d1=close_dist(l,mid);  
37     double d2=close_dist(mid+1,r);  
38     double d=min(d1,d2);
39     cnt1=cnt2=0;   
40     for(int i=l;i<=mid;i++){
41         double dd=a[t[mid]].x-a[t[i]].x;  
42         if(dd<d && dd>=0) c1[++cnt1]=t[i];  
43     }      
44     for(int i=mid+1;i<=r;i++){
45         int dd=a[t[i]].x-a[t[mid]].x;  
46         if(dd<d && dd>=0) c2[++cnt2]=t[i];  
47     }  
48     
49     return calc(l,r,mid,d);
50 }     
51 int main(){
52     while (scanf("%d",&n)!=EOF){
53         if(n==0) break;  
54         for(int i=1;i<=n;i++)  
55             scanf("%lf%lf",&a[i].x,&a[i].y);  
56         for(int i=1;i<=n;i++) t[i]=i;  
57         sort(t+1,t+n+1,cmpx);  
58         printf("%0.2lf\n",close_dist(1,n)/2);  
59     }
60     return 0; 
61 } 
View Code