查看HDU/1007的源代码 ←HDU/1007

[[分类:二分与分治‎]][[分类:计算几何]]
==摘要==
{{信息题|Quoit Design|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}68572#problem/H|2|100|time=2015-02-06 21:36:45}}
*来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=68572 Only a signing tool !] H题
*原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1007

==题意==
求平面内的最近点对。
==题解==
*只能想到O(<m>n^2</m>)的枚举，肯定会T，于是想一定有特别的至少O(nlogn)级别的算法，于是就……<ref>http://yzmduncan.iteye.com/blog/1432880</ref>
*要降复杂度，肯定要使用分治的方式将一维降成logn级别，简单地说有以下3步：
::#将n个点的集合S按x坐标对半分成两个子集S1、S2；
::#递归求S1、S2中答案d；
::#求S1和S2之间的最接近点对，如果比d优更新d。
*比较麻烦的是第三步，为了保证最优性，事实上我们只需要在S1、S2交界线两边形成的宽为2d的带状区间P1、P2查找最优答案即可，但是最坏情况可能有n个点使得复杂度达到O(<m>n^2</m>)。
*但是，由于之前的递归，保证了P1、P2中的点具有两两间距>d这一稀疏的性质，对于P1中的任意一点，P2中的点必定落在一个d*2d的矩形中才可能保持更优，因而最多只需检查六个点<ref>http://blog.csdn.net/lu1012123053/article/details/9825175</ref>。
*我们可以通过对y坐标再次排序来求得这些点。实际时间复杂度约O(nlognlogn)。

==代码==
{{折叠|1007.cpp代码已折叠
|<pre>
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
using namespace std;
#define ci const int &
#define cd const double &
#define cv const Vector2 &
class Vector2
{
public:
    double x,y;
    Vector2(cd _x,cd _y):x(_x),y(_y){};
    Vector2():x(0),y(0){};
    friend Vector2 operator -(cv lhs,cv rhs)
    {
        return Vector2(lhs.x-rhs.x,lhs.y-rhs.y);
    }
    operator double() const
    {
        return sqrt(x*x+y*y);
    }
} p[120000]={};
Vector2 *inRange[120000]={};
size_t k;
bool cmpy(Vector2 *x,Vector2 *y){return x->y<y->y;}
bool cmpx(const Vector2 &x,const Vector2 &y){return x.x==y.x?x.y<y.y:x.x<y.x;}
double getAns(ci l,ci r)
{
    if(l==r)return 1e+9;
    if(l==r-1)return double(p[r]-p[l]);
    int m=(l+r)>>1;
    double rt=min(getAns(l,m),getAns(m+1,r));
    k=0;
    for(int i=l;i<=r;++i)
    {
        if(abs(p[m].x-p[i].x)<=rt)
            inRange[++k]=&p[i];
    }
    sort(inRange+1,inRange+k+1,cmpy);
    for(int i=1;i<=k;++i)
        for(int j=i+1;j<=k&&inRange[j]->y-inRange[i]->y<rt;++j)
            rt=min(double(*inRange[i]-*inRange[j]),rt);
    return rt;
}
int main()
{
    while(1)
    {
        int n;
        scanf("%d",&n);
        if(!n)return 0;
        for(int i=1;i<=n;++i)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        sort(p+1,p+n+1,cmpx);
        printf("%.2lf\n",getAns(1,n)/2);
    }
}
</pre>
|code1007}}

==参考资料和拓展阅读==
<references/>