HDU/1007 2015年2月7日 (六) 15:55云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

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

• 来自寒假练习：Only a signing tool ! H题
• 原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1007

题意

求平面内的最近点对。

题解

• 只能想到O()的枚举，肯定会T，于是想一定有特别的至少O(nlogn)级别的算法，于是就……
• 要降复杂度，肯定要使用分治的方式将一维降成logn级别，简单地说有以下3步：

1. 将n个点的集合S按x坐标对半分成两个子集S1、S2；
2. 递归求S1、S2中答案d；
3. 求S1和S2之间的最接近点对，如果比d优更新d。

• 比较麻烦的是第三步，为了保证最优性，事实上我们只需要在S1、S2交界线两边形成的宽为2d的带状区间P1、P2查找最优答案即可，但是最坏情况可能有n个点使得复杂度达到O()。
• 但是，由于之前的递归，保证了P1、P2中的点具有两两间距>d这一稀疏的性质，对于P1中的任意一点，P2中的点必定落在一个d*2d的矩形中才可能保持更优，因而最多只需检查六个点。
• 我们可以通过对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); } }