分治法解决最近点对问题_the distance between the nearest point pair-程序员宅基地

技术标签: 算法  # 算法-分治  

在一个平面当中分布着n个点。现在我们知道这n个点的坐标,要求找出这n个点当中距离最近的两个点的间距。

我们可以先从一维的寻找最近点寻找思路:
伪代码:

NearestPointPairDim1(A[0,...,n-1]) {
    
    if (n = 1) 
        return INF;
    if (n = 2)
        return d(A[0],A[1]);
    d1 = NearestPointDim1(A[0,...,(n/2)-1]);
    d2 = NearestPointDim1(A[n/2,...,n-1]);
    d3 = d(A[(n/2)-1,n/2]);
    return min(d1,d2,d3);
}

既然一维可以用分治法解决,那二维当然也是可以。
点集合 { ( x i , y i ) } i = 1 N \{(x_i,y_i)\}_{i=1}^N { (xi,yi)}i=1N
算法思想:
  将点集合内的点按 x x x坐标排序,然后按照中点进行划分,从而我们只要求出左边部分的最近点对,右边部分的最近点对,以及一个点在左边一个点在右边的最近点对,最后再取最小距离的就是总体的最近点对。
  通过递归我们可以求左边部分的最近点对的距离 D 1 D_1 D1和右边部分的最近点对的距离 D 2 D_2 D2,我们取 D = m i n ( D 1 , D 2 ) D=min(D_1,D_2) D=min(D1,D2),现在我们来考虑一个点在左边一个点在右边的最近点对这种情况:

  像图片中的这种情况,如果要与左边的 p p p点构成最近点对,则只要在虚线框的部分找就可以,那么虚线框里的点数会不会等于 N 2 \frac{N}{2} 2N,答案是不会的。
在这里插入图片描述
  我们来看这张图,如果要在长方形里(包括边框)里放七个点,根据鸽巢原理,那么一定可以找得到两点 A A A B B B,使得 ∣ A B ∣ < D |AB|<D AB<D,所以要使得虚线框能够形成,那么虚线框里的点不能够多于7个。也就是说对于点 p p p,我们在中线右侧最多只能找出6个点来构成最短点对。
  然后接下来我们就要来找着六个点,对已经按x坐标排好序的点,从中线往左寻找在 D D D范围内的点在数组中的下标 L L L,从中线往右寻找在 D D D范围内的点在数组中的下标 R R R,然后计算 p t s [ L ] pts[L] pts[L] p t s [ R ] pts[R] pts[R]之间中是否存在比 D D D距离更小的最近点对。

#include<vector>
#include<map>
#include<math.h>
#include<iostream>
#include <unordered_map>
#include<algorithm>
using namespace std;
#define INF 0x7fffffff
#define goleft true
#define goright false
int getDist(pair<int,int> A, pair<int,int> B) {
    
    return (A.first - B.first)*(A.first - B.first) + (A.second - B.second)*(A.second - B.second);
}
int getPos(int left,int right,vector<pair<int,int>>& vec,int D,bool GOLeft) {
    
    if(GOLeft){
    
        for (int i = right-1; i>=left; --i){
    
            int xdist = abs(vec[right].first - vec[i].first);
            if(xdist<D)
                return i;
        }
    }
    else {
    
        for (int i = left+1; i<=right; ++i){
    
            int xdist = abs(vec[right].first - vec[i].first);
            if(xdist<D)
                return i;
        }        
    }
    return -1;
}
vector<int> divide (vector<pair<int,int>>& vec, int left, int right) {
    
    if(left == right) {
    
        vector<int> res = {
    INF, -1, -1};
        return res;
    }
    if(left == right - 1) {
    
        vector<int> res = {
    getDist(vec[left], vec[right]), left, right};
        return res;
    }
    vector<int> d1= divide(vec, left, ((right+left) / 2) - 1);
    vector<int> d2= divide(vec, (right+left) / 2, right);
    int d = 0;
    int point1;
    int point2;
    if(d1[0]>d2[0]){
    
        d = d2[0];
        point1 = d2[1]; 
        point2 = d2[2];
    }
    else {
    
        d = d1[0];
        point1 = d1[1]; 
        point2 = d1[2];
    }
    int l = getPos(left, (right + left) / 2, vec, d, goleft);
    int r = getPos((right + left) / 2, right, vec, d, goright);
    for (int i = l; i < (right + left) / 2;++i){
    
        if(l==-1||r==-1)
            break;
        int count = 0;
        for (int j = (right + left) / 2; j <=r;++j) {
    
            int temp = getDist(vec[i], vec[j]);
            if(count>7)
                break;
            ++count;
            if(temp < d){
    
                d = temp;
                point1 = i; 
                point2 = j;
            }
        }
    }
    vector<int> dPoint = {
    d, point1, point2};
    return dPoint;
}

int main() {
    
    // int n;
    // cin >> n;
    // int x, y;
    // vector<pair<int,int>> point;
    // for (int i = 0; i < n; ++i) {
    
    //     cin >> x >> y;
    //     point.push_back(make_pair(x,y));
    // }
    vector<int> xpts = {
    0, 1,  5, 12, 17, 21, 24, 6, 19, 3, 9, 15, 7, 11, 6, 16};
    vector<int> ypts = {
    4, 9, 11, 12, 12,  9,  7, 0,  1, 8, 9,  8, 6,  6, 2,  2};
    vector<pair<int, int>> pts;
    for (int i = 0; i < xpts.size(); ++i) {
    
        pts.push_back(make_pair(xpts[i], ypts[i]));
    }
    sort(pts.begin(), pts.end());
    for(auto p:pts){
    
        cout << p.first << "," << p.second << endl;
    } 
    vector<int> d = divide(pts, 0, pts.size() - 1);
    cout << d[0] << endl;
    cout << pts[d[1]].first << "," <<pts[d[1]].second<< endl;
    cout << pts[d[2]].first << "," << pts[d[2]].second << endl;
    system("pause");
    return 0;
}

杭电1007

Have you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.
Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45699092/article/details/120706843

智能推荐

Java8 parallelStream——共享线程池对性能解析_jdk8 parallelstream 性能-程序员宅基地

文章浏览阅读3.3k次,点赞2次,收藏8次。最近做压测中发现一个应用中cpu过高,导致接口超时rt情况有些不大稳定,jstack打印线程一直在parallelStream相关的代码出进行计算。故对parallelStream相关做一下研究,找一下优化方法。java8并行流parallelStream,相信很多人都喜欢用,特别方便简单。但是有多少人真正知道里面采用的共享线程池对密集型任务,高并发下的性能影响呢可能你的一个应用里面..._jdk8 parallelstream 性能

C++ 11 创建和使用 unique_ptr_unique_ptr创建空节点-程序员宅基地

文章浏览阅读292次。https://www.cnblogs.com/DswCnblog/p/5628195.htmlunique_ptr 不共享它的指针。它无法复制到其他 unique_ptr,无法通过值传递到函数,也无法用于需要副本的任何标准模板库 (STL) 算法。只能移动unique_ptr。这意味着,内存资源所有权将转移到另一 unique_ptr,并且原始 unique_ptr 不再拥有此资源。我们建议..._unique_ptr创建空节点

NetCoreAPI配置全局路由_selector.attributeroutemodel.template-程序员宅基地

文章浏览阅读853次。1:新增类:RouteConvention,继承自IApplicationModelConvention/// <summary> /// 全局路由前缀配置 /// </summary> public class RouteConvention : IApplicationModelConvention { /// <summary> /// 定义一个路由前缀变量 /// </su_selector.attributeroutemodel.template

算 数-程序员宅基地

文章浏览阅读64次。从woody那里copy一段最简的fib代码[code="ruby"]x,y = 0,1 Array.new(10) {|i| [0,1].include?(i) ? 1 : (x,y = y,x+y)&&(x+y) } [/code]生成了这么多,太多了,中途终止了,不知道多少条。[code="ruby"] 1, 1, 2, ..._359579325206583560961765665172189099052367214309267232255589801

Java的BIO和NIO很难懂?用代码实践给你看,再不懂我转行!-程序员宅基地

文章浏览阅读280次。本文原题“从实践角度重新理解BIO和NIO”,原文由Object分享,为了更好的内容表现力,收录时有改动。1、引言这段时间自己在看一些Java中BIO和NIO之类的东西,也看了很多博客,发现各种关于NIO的理论概念说的天花乱坠头头是道,可以说是非常的完整,但是整个看下来之后,发现自己对NIO还是一知半解、一脸蒙逼的状态(请原谅我太笨)。基于以上原因,..._java bio粘包处理

Python3.9环境搭建RobotFramework_python-3.9.9-amd64用那个版本ride-程序员宅基地

文章浏览阅读9k次,点赞2次,收藏12次。Robot Framework是一个基于Python的,可扩展的关键字驱动的测试自动化框架,用于端到端验收测试和验收测试驱动开发(ATDD)。_python-3.9.9-amd64用那个版本ride

随便推点

Hbase相关操作_hbase 查询-程序员宅基地

文章浏览阅读2.4k次。1.进入shellhbase(main):003:0>hbase shell2.查看所有表hbase(main):003:0> list3.根据rowKey查询某个记录hbase(main):003:0>get '表名','rowKey'4.常用过滤器过滤方式是通过value过滤,匹配出value含7259的数据。scan 'buss_surface', FILTER=>"ValueFilter(=,'substring:7259')"过滤方式是通_hbase 查询

噪声:Practical Poissonian-Gaussian noise modeling and fitting for single-image raw-data-程序员宅基地

文章浏览阅读2k次,点赞4次,收藏16次。Practical Poissonian-Gaussian noise modeling and fitting for single-image raw-data文章目录Practical Poissonian-Gaussian noise modeling and fitting for single-image raw-dataPoissonian-Gaussian ModelingThe Noise Profile AlgorithmWavelet domain analysisSegmentat_practical poissonian-gaussian noise modeling and fitting for single-image ra

计算机开机最快设置,w7提高开机速度如何操作_win7电脑怎么开机更快-程序员宅基地

文章浏览阅读4k次。由于win7电脑使用时间过长或者存放时间久了,难免会出现硬件各方面的老化或者堆积了大量的垃圾,因此就会导致电脑开机时的速度有所降低,对此有些用户就想,在不更换硬件的条件下,有没有方法能够提高一下开机速度,那么win7电脑提高开机速度如何操作呢?这里小编就来告诉大家win7电脑开机更快操作步骤。具体方法:1、在任意界面按下:windows键+R,然后在框内输入msconfig,点确定2、然后选择“启..._如何提高w7系统的开机速度

1688API接口:item_search - 按关键字搜索商品_1688 一件代发 api-程序员宅基地

文章浏览阅读672次。今天分享的是1688平台API,item_search - 按关键字搜索商品接口1688的API开发接口,我们需要做下面几件事情。1)开放平台注册开发者账号;2)然后为每个1688应用注册一个应用程序键(App Key) ;3)下载1688API的SDK并掌握基本的API基础知识和调用;4)利用SDK接口和对象,传入AppKey或者必要的时候获取并传入SessionKey来进行程序开发;5)利用1688平台的文档中心和API测试工具,对接口进行测试。从而了解返回信息,方便程序获取1688_1688 一件代发 api

vue-property-decorator使用指南_vue-property-decorator emit update-程序员宅基地

文章浏览阅读3.1k次,点赞2次,收藏12次。在Vue中使用TypeScript时,非常好用的一个库,使用装饰器来简化书写。一、安装npmi-Svue-property-decorator@Prop @PropSync @Provide @Model @Watch @Inject @Provide @Emit @Component(provided byvue-class-component) Mixins(the helper function namedmixinsprovided byvue-cla..._vue-property-decorator emit update

(七)用ChartDirector绘制实时图表-程序员宅基地

文章浏览阅读467次。本示例演示如何用Web图表控件 ChartDirector 绘制一个配置有刷新率的实时图表。在本例中,由一个计时器驱动的随机数生成器生成新的数据值,新产生的值会转换到数据数组中,然后显示在图表上。图表由一个秒表进行更新,这样图表的刷新率可独立于数据率。此外,这个图表支持暂停以方便用户查看,但是后台的数据仍然在继续更新。图表刷新计时器调用CChartViewer.update..._c++ chartdirect updateviewport