精华内容
下载资源
问答
  • 平面最近点对

    2020-03-11 11:46:40
    平面最近点对 平面最近点对问题是指:求平面内n个点中距离最近的两点间距离。 分治求法: 首先将n个点按以x为第一关键字,y为第二关键字降序排序,然后选取第n/2个点为分割点,分治求左边n/2个点和右边n-n/2个点的...

    平面最近点对

    平面最近点对问题是指:求平面内n个点中距离最近的两点间距离。
    分治求法:
    首先将n个点按以x为第一关键字,y为第二关键字降序排序,然后选取第n/2个点为分割点,分治求左边n/2个点和右边n-n/2个点的平面最近点对,那么答案的范围肯定包括了左边右两边的最近点对了。d=min(rd,ld)d=min(rd,ld).那么d是当前整个平面的最近点对的距离了吗?

    答案不是,分治还需要合并!!
    在这里插入图片描述

    最近点对也可能在中间。
    在这里插入图片描述
    下一步以n/2为中间点将x坐标左右d矩形内(缩小范围)的统计下来以,y坐标排序O(n2)O(n^2)计算这些点的最近距离。

    奇袭

    在与联盟的战斗中屡战屡败后,帝国撤退到了最后一个据点。
    依靠其强大的防御系统,帝国击退了联盟的六波猛烈进攻。
    经过几天的苦思冥想,联盟将军亚瑟终于注意到帝国防御系统唯一的弱点就是能源供应。
    该系统由N个核电站供应能源,其中任何一个被摧毁都会使防御系统失效。
    将军派出了N个特工进入据点之中,打算对能源站展开一次突袭。
    不幸的是,由于受到了帝国空军的袭击,他们未能降落在预期位置。
    作为一名经验丰富的将军,亚瑟很快意识到他需要重新安排突袭计划。
    他现在最想知道的事情就是哪个特工距离其中任意一个发电站的距离最短。
    你能帮他算出来这最短的距离是多少吗?
    输入格式
    输入中包含多组测试用例。
    第一行输入整数T,代表测试用例的数量。
    对于每个测试用例,第一行输入整数N。
    接下来N行,每行输入两个整数X和Y,代表每个核电站的位置的X,Y坐标。
    在接下来N行,每行输入两个整数X和Y,代表每名特工的位置的X,Y坐标。
    输出格式
    每个测试用例,输出一个最短距离值,结果保留三位小数。
    每个输出结果占一行。
    数据范围
    1N100000,0X,Y10000000001≤N≤100000, 0≤X,Y≤1000000000

    输入样例:

    2  
    4  
    0 0  
    0 1  
    1 0  
    1 1  
    2 2  
    2 3  
    3 2  
    3 3  
    4  
    0 0  
    0 0  
    0 0  
    0 0  
    0 0  
    0 0  
    0 0  
    0 0  
    

    输出样例:

    1.414  
    0.000
    

    思路:设核电站彼此之间和特工彼此之间的距离为inf,求核电站和特工之间的最近点对。

    #include<bits/stdc++.h>
    using namespace std;
    const double inf=1000000000000;
    const double eps=1e-6;
    struct node{
        double x,y;
        int type;
    }p[200010];
    int tmp[200010];
    double dis(int a,int b){
        if(p[a].type==p[b].type)
            return inf;
        else
        return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
    }
    bool cmpxy(node a,node b){
        if(fabs(a.x-b.x)<eps) return b.y-a.y>eps;
        else return b.x-a.x>eps;
    }
    bool cmpy(int a,int b){
        return p[a].y<p[b].y;
    }
    double Closest_Pair(int left,int right){
        if(left==right) return inf;
        if(left+1==right) return dis(left,right);
        int mid=(left+right)/2;
        double d=Closest_Pair(left,mid);
        d=min(d,Closest_Pair(mid+1,right));
        int k=0;
        for(int i=left;i<=right;++i){
            if(d-fabs(p[mid].x-p[i].x)>eps){
                tmp[k++]=i;
            }
        }
        sort(tmp,tmp+k,cmpy);
        for(int i=0;i<k;++i){
            for(int j=i+1;j<k;++j){
                int t1=tmp[i],t2=tmp[j];
                if(p[t1].type!=p[t2].type&&d-fabs(p[t1].y-p[t2].y)>eps){
                    double td=dis(t1,t2);
                    d=min(d,td);
                }
            }
        }
        return d;
    }
    int main(){
        int T;
        cin>>T;
        while(T--){
            int n;
            cin>>n;
            for(int i=1;i<=n;++i){
                cin>>p[i].x>>p[i].y;
                p[i].type=1;
            }
            for(int i=n+1;i<=n*2;++i){
                cin>>p[i].x>>p[i].y;
                p[i].type=2;
            }
            sort(p+1,p+1+2*n,cmpxy);
            printf("%.3f\n",Closest_Pair(1,2*n));
        }
        return 0;
    }
    
    
    展开全文
  • 平面最近点对1.zip

    2021-04-21 19:25:18
    分治法求平面最近点对
  • 平面最近点对问题

    2020-04-23 17:57:30
    平面最近点对问题求解—基于Java语言   1. 问题描述: 本问题来自《编程之美2.11—寻找最近点对》,文中给出了两种解法:暴力解法,分治解法。其中,暴力解法很简单,求出所有点之...

    平面最近点对问题求解—基于Java语言

     

    1. 问题描述:

    本问题来自《编程之美2.11—寻找最近点对》,文中给出了两种解法:暴力解法,分治解法。其中,暴力解法很简单,求出所有点之间的距离并做比较,便可找到距离最小的点对;当然,这不是最优解,时间复杂度为O(n^2)。文中还介绍了分治法,不过,没有给出源代码,网上的解法也多是基于C写的,本文将基于Java用分治法解决这个问题。

    2.分治法解法思想

    分治法思路: 
    1) 把它分成两个或多个更小的问题; 
    2) 分别解决每个小问题; 
    3) 把各小问题的解答组合起来,即可得到原问题的解答。小问题通常与原问题相似,可以递归地使用分而治之策略来解决。

    这里的分治算法的主要思路是将平面上的n个点分为两个子集S1,S2。每个子集中有n/2个点,然后递归的在每个子集中求解最近点对,两边求得的结果如图所示:

    这里写图片描述

    那么可以看出左边的最近点对的距离为d1,右边为d2。但是最近对可能一个点在S1中而另一个点在S2中。这样,我们,就要去想办法对其进行合并,然后求得合并区域的最近对距离,假设为d3,那么只需要比较d1,d2,d3的大小关系即可,最小的就是平面最近对的距离。通过分析我们可以知道,如果存在这样的最近对的点,那么这个点在S1集合中,肯定是横坐标最靠近中位线 L 的点,S2中同理。那么这个范围如何划定呢?


    d=min(d1,d2)假定中位线横坐标为X,那么范围就是[X-d,X+d].这个范围是怎么划定的呢?根据平面中点的位置我们就可以知道,两点的距离为横纵坐标之间的差值的平方和。那么如果要存在这样的点,他们之间的横坐标之间的差值的绝对值必须要小于等于d(这里包括这点恰好就在中位线 L 上)。这样可以筛选出横坐标为[X-d,X+d]的区域。如下图所示:


    这里写图片描述

    可以看出这个区域中包含三个点,只需要求出这三个点之间的最近点对即可(蛮力法)。这里还需要注意一点,上面是通过横坐标筛选的这个区域,这里可以根据纵坐标将纵坐标差的绝对值大于 d 的坐标剔除。

     

    3. 基于分治法的解法代码

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.List;
     
    public class MinDis
    {
     
        public static void main(String[] args)
        {
            // 测试用例
            Point[] points = new Point[7];
     
            points[0] = new Point(1, 1);
            points[1] = new Point(1, 9);
            points[2] = new Point(2, 5);
            points[3] = new Point(3, 1);
            points[4] = new Point(4, 4);
            points[5] = new Point(5, 8);
            points[6] = new Point(6, 2);
     
            // 预处理,基于x轴坐标排序,便于分治法实施
            Arrays.sort(points, new Comparator<Point>()
            {
                @Override
                public int compare(Point p1, Point p2)
                {
                    return (p1.x > p2.x) ? 1 : (p1.x == p2.x) ? 0 : -1;
                }
     
            });
            // 测试
            System.out.println(divide(0, points.length-1, points));
        }
        
        /**
         * 求平面上距离最近的两个点
         * 
         */
        public static double divide(int left, int right, Point[] points)
        {
            // 当前最小两点距离,初始值设置为无穷大
            double curMinDis = 1e20;
            // 如果只有一个点,则不存在最近两点距离,返回无穷大
            if (left == right)
            {
                return curMinDis;
            }
            // 这里是判断是否为只有两个点,如果只有两个点的话那么直接求解。
            if (left + 1 == right)
            {
                return distance(points[left], points[right]);
            }
     
            // 分治法:第一步:分区,并求取左右分区最小两点距离
            // 通过右移运算除2,对区域进行合理的划分,使得左右两边保持大致相等个数点
            int middle = (left + right) >> 1;
            double leftMinDis = divide(left, middle, points);
            double rightMinDis = divide(middle, right, points);
     
            curMinDis = (leftMinDis <= rightMinDis) ? leftMinDis : leftMinDis;
     
            // 分治法:第二步:假设距离最近的两点分别在左右分区中
            // 关键代码,距离最近的两个点,一个位于左边区域,一个位于右边区域,x轴搜索范围[middle-curMinDis, middle+curMinDis]
            // 记录搜索区间内的点的索引,便于进一步计算最小距离
            List<Integer> validPointIndex = new ArrayList<>();
            for (int i = left; i <= right; i++)
            {
                if (Math.abs(points[middle].x - points[i].x) <= curMinDis)
                {
                    validPointIndex.add(i);
                }
            }
            // 基于索引,进一步计算区间内最小两点距离
            for (int i = 0; i < validPointIndex.size() - 1; i++)
            {
                for (int j = i + 1; j < validPointIndex.size(); j++)
                {
                    // 如果区间内的两点y轴距离大于curMinDis,则没必要计算了,因为,它们的距离肯定大于curMinDis,
                    if (Math.abs(points[validPointIndex.get(i)].y
                            - points[validPointIndex.get(j)].y) > curMinDis)
                    {
                        continue;
                    }
                    double tempDis = distance(points[validPointIndex.get(i)],
                            points[validPointIndex.get(j)]);
     
                    curMinDis = (tempDis < curMinDis) ? tempDis : curMinDis;
                }
            }
     
            return curMinDis;
        }
     
        /**
         * 计算两点间的距离
         */
        public static double distance(Point p1, Point p2)
        {
            return Math.sqrt((p2.y - p1.y) * (p2.y - p1.y) + (p2.x - p1.x) * (p2.x - p1.x));
        }
    }
    /**
     * 定义点
     * 
     */
    class Point
    {
        public int x;
        public int y;
     
        Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }
    

    特别说明:

    本文部分内容摘录自博客:https://blog.csdn.net/Up_junior/article/details/52019943

    ————————————————
    原文链接: https://blog.csdn.net/Jin_Kwok/article/details/82350019.

    展开全文
  • 平面最近点对

    前言

    这题是NOIP时期做的
    但是那时候比较傻逼,于是没有认真想证明
    然后今天我在作bzoj的一道题的时候回忆起了这道题。。
    然后发现不是很记得了
    于是赶紧补了一发

    题意

    就是给你n个点,要你求最近公共点对

    题解

    我们考虑分治,先按x进行排序
    然后我们先处理两边的答案,设得到了两个答案d1,d2,然后令d=min(d1,d2)
    然后最后考虑跨过中垂线的答案
    明显地,你距离中垂线的距离不可以超过d
    然后我们就得到了左边一些点,右边一些点
    然后我们暴力枚举左边的点,然后去暴力和右边的点匹配
    但是,这里有一个优化
    因为我们知道,之前的最小值是d了
    所以,如果我们左边的点要匹配,那么他有右边的点肯定是在他一个d2d的矩阵里
    比如下面这个丑陋的图
    黄色线是分治的分割线,然后红色是一个矩阵,当然,在点的下面还有一个,我就不画了
    这里写图片描述
    然后在分割线右边的,就是一个最大就是dd的矩阵
    但是我们又知道,右边的点,距离肯定是不会小于d的
    于是我们考虑,对于一个dd的矩阵,能选择多少个点,使得里面任意两个点的距离不小于d
    可以发现,最多只有4个,就是选择四个顶点。
    所以两个矩阵最多只有8个
    其实有两个还是重复的,所以只有6个
    所以我们可以按y排序,然后对于每一个点,就暴力扫他可能产生答案的6个点就可以了

    时间复杂度O(8nlogn)如果大家写块排的话就会多一个log

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    using namespace std;
    const int N=200005;
    const double MAX=(1LL<<55);
    int n;
    struct qq
    {
        double x,y;
    }s[N];
    bool cmpx (qq a,qq b){return a.x<b.x;}
    bool cmpy (qq a,qq b){return a.y<b.y;}
    qq lalal[N];
    double dis (qq a,qq 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 MAX;
        int mid=(l+r)>>1;
        double d1=solve(l,mid);
        double d2=solve(mid+1,r);
        double d=min(d1,d2);
        int tot=0;
        for (int u=l;u<=r;u++)
            if (abs(s[u].x-s[mid].x)<=d)
                lalal[++tot]=s[u];
        sort(lalal+1,lalal+1+tot,cmpy);
        for (int u=1;u<=tot;u++)
            for (int i=u+1;i<=tot&&lalal[i].y-lalal[u].y<d;i++)
            {
                double d3=dis(lalal[i],lalal[u]);
                if (d>d3)   d=d3;
            }
        return d;
    }
    int main()
    {
        scanf("%d",&n);
        for (int u=1;u<=n;u++)  scanf("%lf%lf",&s[u].x,&s[u].y);
        sort(s+1,s+1+n,cmpx);
        printf("%.4lf\n",solve(1,n));
        return 0;
    }
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,266
精华内容 506
关键字:

平面最近点对