（以“分类:二分与分治分类:计算几何 ==摘要== {{信息题|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 | + | {{信息题|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 | ||
| + | |||
==题意== | ==题意== | ||
求平面内的最近点对。 | 求平面内的最近点对。 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| Quoit Design | ★★☆☆☆ | 答案正确 | 100 | 2015-02-06 21:36:45 | 无 |
求平面内的最近点对。
比较麻烦的是第三步，为了保证最优性，事实上我们只需要在S1、S2交界线两边形成的宽为2d的带状区间P1、P2查找最优答案即可，但是最坏情况可能有n个点使得复杂度达到O()。
但是，由于之前的递归，保证了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);
}
}
|
CloudLunar