即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

AOJ 862 平面上最近点对

编程语言 wenjoor 25℃ 0评论
本文目录
[隐藏]

1.平面上最近点对

http://ccpc.ahu.edu.cn:8080/OJ/Problem.aspx?id=862

分治思想, 核心是分治算法

  1. 分别根据点的 x,y 值进行排序

  2. 在 x 轴上划一道垂线, 将点均分成两半

  3. 假设最近点对都在左/右部分, 递归计算左/右半部分的最短距离


    并返回较小值 dis

  4. 假设最近点对分别在左右两个部分, 横跨中心的竖线. 中心线为中心,


    2*dis 为宽度画一个矩形, 横跨中心线的最近点对 candidate 都在这个矩形内.


    将这些点按照 y 值的大小加入到数组中. 遍历数组中的点, 将该点与其后的


    7 个点计算距离, 返回最小距离

  5. 为什么仅和 7 个点作对比呢. 因为已经假设 dis 是左右不分最近点对的最小值,


    这就说明在一个长(宽)为 dis 的正方形内, 至多有 4 个点. 长为 dis*2,


    宽为 dis 的长方形至多 8 个.

#include 
#include 
#include 
#include
#include 
using namespace std;

const double INF =1e20;
const int N=100005;

struct Point
{
double x;
double y;
}point [N];

int n;int tmpt[N];


double min2(double a, double b)
{
    return a < b ? a : b;
}

int cmpxy(const void *a,const void *b)
{
    Point *c=(Point *)a;
    Point *d=(Point *)b;
    if(c->x!=d->x)
        return c->x-d->x;
    return c->y-d->y;
}

int cmpy(const void *a,const void *b)
{
    int c=*(int*)a,d=*(int *)b;
    return point[c].y-point[d].y;
}

double dis(int i,int j)
{
    //return sqrt((point[i].x-point [j].x)*(point[i].x-point [j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));
        return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));

}

double Closest(int left,int right)
{
    double d=INF;
    if(left==right)return d;
    if(left+1==right)return dis(left,right);
    int mid=(left+right)/2;
    double d1=Closest(left,mid);
    double d2=Closest(mid+1,right);
    d=min2(d1,d2);
    int i,j,k;
    for( i=left,k=0;i<=right;i++)
    {
        if(abs(point[mid].x-point[i].x)<=d)
            tmpt[k++]=i;
    }
    qsort(tmpt,k,sizeof(int),cmpy);
    for(int i=0;ifor(int j=i+1;jif(point[tmpt[j]].y-point[tmpt[i]].ydouble d3=dis(tmpt[i],tmpt[j]);
            if(d3return d;
}

int main()
{
    scanf("%d",&n);
    if(n)
    {
        for(int i=0;iscanf("%lf%lf",&point[i].x,&point[i].y);
        qsort(point,n,sizeof(Point),cmpxy);
        printf("%.4lf\n",Closest(0,n-1));
        //scanf("%d",&n);
    }
    return 0;
}

转载请注明:CodingBlog » AOJ 862 平面上最近点对

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情