2013-team5/minpair

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 求二维平面最近点对 ===

{{{
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double INF=1e30;
struct point{ double x,y; };
inline double sqr(double x){ return x * x; }
inline double dis(point a,point b){ return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); }
inline int cmpx(point a,point b){ return a.x<b.x || a.x==b.x && a.y<b.y; }

class Minpair{
public:
    static const int SIZE=100005;//数据范围
    point X[SIZE],Y[SIZE],Q[SIZE];
    int tot;
    double res;
    void clear(){ tot=0; }//清空
    inline void add(point a){ X[tot]=a; tot++; }//加入一个点
    double divide(int l,int r,point &a,point &b){
        if (l>=r) return INF;
        int m=(l+r)>>1;
        double xl=X[m+1].x,xr=X[m].x;
        divide(l,m,a,b);
        divide(m+1,r,a,b);
        int tl=l,tr=m+1;
        for (int i=l; i<=r; i++)
            if (tr>r || tl<=m && X[tl].y<X[tr].y)
                Y[i]=X[tl++];
            else
                Y[i]=X[tr++];

        xl-=res; xr+=res;
        int ll=0,rr=-1;
        for (int i=l; i<=r; i++)
            if (xl<Y[i].x && Y[i].x<xr){
                while(ll<=rr && Y[i].y-Q[ll].y>=res) ll++;
                for (int j=ll; j<=rr; j++){
                    double tmp=dis(Y[i],Q[j]);
                    if (tmp<res){
                        res=tmp;
                        a=Y[i]; b=Q[j];
                    }
                }
                Q[++rr]=Y[i];
            }
        for (int i=l; i<=r; i++) X[i]=Y[i];
        return res;
    }
    double Mindis(point& a,point& b){//最近点对返回到point a,b. 返回值为a,b之间的距离
        sort(X,X+tot,cmpx);
        res=INF;
        return divide(0,tot-1,a,b);
    }
};
}}}

{{{
///zoj2107, 800ms 

Minpair P;

int main(){
    int n;
    while (scanf("%d",&n)!=EOF){
        if (n==0) break;
        P.clear();
        for (int i=0; i<n; i++){
            point a;
            scanf("%lf%lf",&a.x,&a.y);
            P.add(a);
        }
        point a,b;
        printf("%.2lf\n",P.Mindis(a,b)/2.0);
    }
    return 0;
}
}}}

求二维平面最近点对

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double INF=1e30;
struct point{ double x,y; };
inline double sqr(double x){ return x * x; }
inline double dis(point a,point b){ return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); }
inline int cmpx(point a,point b){ return a.x<b.x || a.x==b.x && a.y<b.y; }
class Minpair{
public:
    static const int SIZE=100005;//数据范围
    point X[SIZE],Y[SIZE],Q[SIZE];
    int tot;
    double res;
    void clear(){ tot=0; }//清空
    inline void add(point a){ X[tot]=a; tot++; }//加入一个点
    double divide(int l,int r,point &a,point &b){
        if (l>=r) return INF;
        int m=(l+r)>>1;
        double xl=X[m+1].x,xr=X[m].x;
        divide(l,m,a,b);
        divide(m+1,r,a,b);
        int tl=l,tr=m+1;
        for (int i=l; i<=r; i++)
            if (tr>r || tl<=m && X[tl].y<X[tr].y)
                Y[i]=X[tl++];
            else
                Y[i]=X[tr++];
        xl-=res; xr+=res;
        int ll=0,rr=-1;
        for (int i=l; i<=r; i++)
            if (xl<Y[i].x && Y[i].x<xr){
                while(ll<=rr && Y[i].y-Q[ll].y>=res) ll++;
                for (int j=ll; j<=rr; j++){
                    double tmp=dis(Y[i],Q[j]);
                    if (tmp<res){
                        res=tmp;
                        a=Y[i]; b=Q[j];
                    }
                }
                Q[++rr]=Y[i];
            }
        for (int i=l; i<=r; i++) X[i]=Y[i];
        return res;
    }
    double Mindis(point& a,point& b){//最近点对返回到point a,b. 返回值为a,b之间的距离
        sort(X,X+tot,cmpx);
        res=INF;
        return divide(0,tot-1,a,b);
    }
};

///zoj2107, 800ms 
Minpair P;
int main(){
    int n;
    while (scanf("%d",&n)!=EOF){
        if (n==0) break;
        P.clear();
        for (int i=0; i<n; i++){
            point a;
            scanf("%lf%lf",&a.x,&a.y);
            P.add(a);
        }
        point a,b;
        printf("%.2lf\n",P.Mindis(a,b)/2.0);
    }
    return 0;
}