(以“分类:二分与分治‎分类:计算几何 ==摘要== {{信息题|Quoit Design|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}68572#problem/H|2|...”为内容创建页面)
 
摘要: 没有错误原因
第1行: 第1行:
 
[[分类:二分与分治‎]][[分类:计算几何]]
 
[[分类:二分与分治‎]][[分类:计算几何]]
 
==摘要==
 
==摘要==
{{信息题|Quoit Design|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}68572#problem/H|2|100|输出格式|0|time=2015-02-06 21:36:45}}
+
{{信息题|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.hust.edu.cn/vjudge/contest/view.action?cid=68572 Only a signing tool !] H题
 
*原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1007
 
*原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1007
 +
 
==题意==
 
==题意==
 
求平面内的最近点对。
 
求平面内的最近点对。

2015年2月7日 (六) 15:39的版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
Quoit Design ★★☆☆☆ 答案正确 100 2015-02-06 21:36:45

题意

求平面内的最近点对。

题解

  • 只能想到O(n^2)的枚举,肯定会T,于是想一定有特别的至少O(nlogn)级别的算法,于是就……
  • 要降复杂度,肯定要使用分治的方式将一维降成logn级别,[1]简单地说有以下3步:
  1. 将n个点的集合S按x坐标对半分成两个子集S1、S2;
  2. 递归求S1、S2中答案d;
  3. 求S1和S2之间的最接近点对,如果比d优更新d。

比较麻烦的是第三步,为了保证最优性,事实上我们只需要在S1、S2交界线两边形成的宽为2d的带状区间P1、P2查找最优答案即可,但是最坏情况可能有n个点使得复杂度达到O(n^2)。 但是,由于之前的递归,保证了P1、P2中的点具有两两间距>d这一稀疏的性质,对于P1中的任意一点,P2中的点必定落在一个d*2d的矩形中才可能保持更优,因而最多只需检查六个点[2]。 我们可以通过对y坐标再次排序来求得这些点。实际时间复杂度约O(nlognlogn)。

代码

1007.cpp代码已折叠
展开折叠内容
#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);
    }
}


参考资料和拓展阅读

  1. http://yzmduncan.iteye.com/blog/1432880
  2. http://blog.csdn.net/lu1012123053/article/details/9825175

著作权声明[编辑]

关于[编辑]