分治算法应用-最近点对的最小距离-hdu 1007 Quoit Design

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了分治算法应用-最近点对的最小距离-hdu 1007 Quoit Design，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1369字，纯文字阅读大概需要2分钟。

内容图文

 

 

采用分治的思想，把n个点按照x坐标进行排序，以坐标mid为界限分成左右两个部分，对左右两个部分分别求最近点对的距离，然后进行合并。对于两个部分求得的最近距离d，合并过程中应当检查宽为2d的带状区间是否有两个点分属于两个集合而且距离小于d，最多可能有n个点，合并时间最坏情况下是O(n^2).但是，左边和右边中的点具有以下稀疏的性质，对于左边中的任意一点，右边的点必定落在一个d*2d的矩形中，且最多只需检查6个点（鸽巢原理），这样，先将带状区间的点按照y坐标进行排序，然后线性扫描，这样合并的时间复杂度为O（nlogn）。

#include <bits/stdc++.h>

using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+10;
int n;
struct Point
{
    double x,y;
} a[N],b[N];

bool cmpx(const Point a,const Point b)
{
    return a.x<b.x;
}

bool cmpy(const Point a,const Point b)
{
    return a.y<b.y;
}

double dis(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}


double solve(int l,int r)
{
    if (l==r)
    {
        return inf;
    }
    int mid=(l+r)>>1,tail=0;
    double d=min(solve(l,mid),solve(mid+1,r));
    for (int i=mid; i>=l&&a[mid].x-a[i].x<d; i--)
    {
        b[tail++]=a[i];
    }
    for (int i=mid+1; i<=r&&a[i].x-a[mid].x<d; i++)
    {
        b[tail++]=a[i];
    }
    sort(b,b+tail,cmpy);
    for (int i=0; i<tail; i++)
    {
        for (int j=i+1; j<tail&&b[j].y-b[i].y<d; j++)
        {
            d=min(d,dis(b[i],b[j]));
        }
    }
    return d;
}



int main()
{
    while (scanf("%d",&n))
    {
        if (!n)
        {
            break;
        }
        for (int i=1; i<=n; i++)
        {
            scanf("%lf%lf",&a[i].x,&a[i].y);
        }
        sort(a+1,a+n+1,cmpx);
        double ans=solve(1,n)/2;
        printf("%.2lf\n",ans);
    }
}

　　

内容总结

以上是互联网集市为您收集整理的分治算法应用-最近点对的最小距离-hdu 1007 Quoit Design全部内容，希望文章能够帮你解决分治算法应用-最近点对的最小距离-hdu 1007 Quoit Design所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---