hdu1007

发表于 | 分类于 ， | 阅读数 次

链接:hdu1007

题解

  • 平面最近点对问题
  • 采用分治,复杂度为O(Knlognlogn)
  • 先考虑一维的情况(虽然可以O(n)扫一遍)
  • 将序列按升序排列,然后划分为两个区间,假设左边最近点对距离为d1 ,右边最近点对距离为d2 d=min(d1,d2)显然不是整个区间的最近点对距离
  • 假设d1,d2已求出的情况下,只需要求出横跨两个区间的最近点对距离d3就好了
  • 显然只有满足dis(p,mid)<d以及dis(q,mid)<d的点才可能会对答案有贡献(p在左区间,q在右区间),求出这部分再按照y轴排序之后在满足y[j]-y[i]<d的点内求就好

  • 具体看代码就好

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    #include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const double dnf=0x3f3f3f3f;
    const int N=1e5+7;
    double x[N],y[N];
    int tmp[N],id[N],cnt,n;
    inline double dis(int a,int b){return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));}
    inline int cmpx(int a,int b){return x[a]==x[b]?y[a]<y[b]:x[a]<x[b];}
    inline int cmpy(int a,int b){return y[a]<y[b];}
    double solve(int l,int r){
        if(l==r)return dnf;
        if(r==l+1)return dis(id[l],id[r]);
        int mid=l+r>>1;
        double d1=solve(l,mid);
        double d2=solve(mid+1,r);
        double d=min(d1,d2);cnt=0;
        rep(i,l,r)if(dis(id[i],id[mid])<=d)tmp[++cnt]=id[i];
        sort(tmp+1,tmp+cnt+1,cmpy);
        rep(i,1,cnt)for(int j=i+1;j<=cnt&&y[tmp[j]]-y[tmp[i]]<d;j++){double tp=dis(tmp[i],tmp[j]);d=min(tp,d);}
        return d;
    }
    int main(){
        while(~scanf("%d",&n)&&n){
            rep(i,1,n){scanf("%lf%lf",&x[i],&y[i]);id[i]=i;}
            sort(id+1,id+n+1,cmpx);
            printf("%.2lf\n",solve(1,n)/2);
        }
        return 0;
    }

  • 看到某个大佬用奇怪的方式O()暴力过了

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    #include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const double dnf=0x3f3f3f3f;
    const int N=1e5+7;
    struct node{
    	double x,y;
    	inline void init(){scanf("%lf%lf",&x,&y);}
    }a[N],b[N];
    int n;
    inline int cmpx(const node &x,const node &y){return x.x<y.x;}
    inline int cmpy(const node &x,const node &y){return x.y<y.y;}
    inline double dis(node &x,node &y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
    int main(){
    	while(~scanf("%d",&n)&&n){
    		double d=dnf;
    		int tot1=0,tot2=100;
    		rep(i,1,n)a[i].init();
    		rep(i,1,n)b[i]=a[i];
    		sort(a+1,a+n+1,cmpx);
    		sort(b+1,b+n+1,cmpy);
    		for(int i1=2,i2=2,j1=1,j2=1;i1<=n&&i2<=n;){
    			repd(k,j1,1){
    				d=min(d,dis(a[i1],a[k]));
    				if(a[i1].x-a[k].x>=d||k==1){j1=i1++;break;}
    				if(tot1>=tot2){tot1+=20;j1=k-1;break;}
    				tot1++;
    			}
    			repd(k,j2,1){
    				d=min(d,dis(b[i2],b[k]));
    				if(b[i2].y-b[k].y>=d||k==1){j2=i2++;break;}
    				if(tot2>=tot1){tot2+=20;j2=k-1;break;}
    				tot2++;
    			}
    		}
    		printf("%.2lf\n",d/2);
    	}
    	return 0;
    }