小 （云璟月移动CodeVS/1007页面至HDU/1007，不留重定向：选错） |
小 （→题解： 排版） |
||
| 第8行： | 第8行： | ||
求平面内的最近点对。 | 求平面内的最近点对。 | ||
==题解== | ==题解== | ||
| − | *只能想到O(<m>n^2</m>)的枚举，肯定会T，于是想一定有特别的至少O(nlogn)级别的算法，于是就…… | + | *只能想到O(<m>n^2</m>)的枚举，肯定会T，于是想一定有特别的至少O(nlogn)级别的算法，于是就……<ref>http://yzmduncan.iteye.com/blog/1432880</ref> |
| − | + | *要降复杂度，肯定要使用分治的方式将一维降成logn级别，简单地说有以下3步： | |
| − | #将n个点的集合S按x坐标对半分成两个子集S1、S2； | + | ::#将n个点的集合S按x坐标对半分成两个子集S1、S2； |
| − | #递归求S1、S2中答案d； | + | ::#递归求S1、S2中答案d； |
| − | #求S1和S2之间的最接近点对，如果比d优更新d。 | + | ::#求S1和S2之间的最接近点对，如果比d优更新d。 |
| − | 比较麻烦的是第三步，为了保证最优性，事实上我们只需要在S1、S2交界线两边形成的宽为2d的带状区间P1、P2查找最优答案即可，但是最坏情况可能有n个点使得复杂度达到O(<m>n^2</m>)。 | + | *比较麻烦的是第三步，为了保证最优性，事实上我们只需要在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>。 | + | *但是，由于之前的递归，保证了P1、P2中的点具有两两间距>d这一稀疏的性质，对于P1中的任意一点，P2中的点必定落在一个d*2d的矩形中才可能保持更优，因而最多只需检查六个点<ref>http://blog.csdn.net/lu1012123053/article/details/9825175</ref>。 |
| − | 我们可以通过对y坐标再次排序来求得这些点。实际时间复杂度约O(nlognlogn)。 | + | *我们可以通过对y坐标再次排序来求得这些点。实际时间复杂度约O(nlognlogn)。 |
| + | |||
==代码== | ==代码== | ||
{{折叠|1007.cpp代码已折叠 | {{折叠|1007.cpp代码已折叠 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| Quoit Design | ★★☆☆☆ | 答案正确 | 100 | 2015-02-06 21:36:45 | 无 |
求平面内的最近点对。
| 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);
}
}
|
CloudLunar