2 wb it man wb_it_man 于 2016.05.06 13:53 提问

类似于最近点对问题,但是有点不一样,麻烦看下我的思路有没有问题

问题:(最近点对问题)设平面上有两个不同的点p1=(x1,y1)和p2(x2,y2),若x1>x2,y1>y2,则称p1支配p2,。
给定平面上n个点的集合P={p1,p2,...,pn},若点pi属于P,不被平面上任意点支配,则称pi为P的最大点。
试使用分治法设计一个O(nlogn)的算法计算P中的所有最大点。

分治法解决最近点对问题思路:
用分治法解决最近点对问题,就是将一个问题分解两个子问题,然后递归处理子问题,然后合并。可能两个点在每个子问题中,也可能两个点分别在两个子问题中,就这两种情况。则基本过程为:找一条中垂线m(坐位S集合x坐标的中位数)把n个元素分成左右两部分元素,然后分别求得两边的最短距离1d,2d,然后取两者中的最小者记为d,在中线两边分别取d的距离,记录该距离范围内点的个数,中线左边有L个元素,右边有R个元素,分别将两边的点按y坐标升序排列,在左边集合中每一个点,找右边集合的点,找到与之距离小于d的点,更新最短距离,直到循环结束,即可求出最短距离。

以上是解决找距离最近的点的问题

解决最开始那个问题,我的思路是:
1.找一条中垂线m(坐位S集合x坐标的中位数)把n个元素分成左右两部分元素。
2.既然已经有了坐标,那么这时中垂线右边的点的x坐标肯定要比左边的大,这时就只需要在中垂线的右边找就可以了
3.取得右边最大距离为d

想到这里不知道接下来该怎么办了
我是初学者,可能有些啰嗦,问题又不是很难,麻烦大家帮我解决一下,谢谢

3个回答

CSDNXIAON
CSDNXIAON   2016.05.06 14:02

有没有问题呢?
----------------------同志你好,我是CSDN问答机器人小N,奉组织之命为你提供参考答案,编程尚未成功,同志仍需努力!

tianlang_2008
tianlang_2008   2016.05.06 15:24

你的目的是找最大点,所以第3步应该是找右边Y值最大的和X值最大的。

wb_it_man
wb_it_man 是不是满足X Y最大,而且是距离最远的点,就是要找的点
大约 2 年之前 回复
wb_it_man
wb_it_man 第三步找右边X最大和Y最大的,但是只有X和Y同时最大才是最大的,这里应该怎么办?
大约 2 年之前 回复
wb_it_man
wb_it_man   2016.05.06 18:40

第三步找右边X最大和Y最大的,但是只有X和Y同时最大才是最大的,这里应该怎么办?

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
【算法导论】【笔记】【分治法】最近点对问题
寻找最近点对 目录 寻找最近点对 问题分析 分治法 时间复杂度 题目:在一个 n≥2n\geq 2 个点的集合 Q 中寻找距离最近的点对 问题分析 首先很容易想到暴力破解的方法,但是需要 O(n2n^2) 的时间复杂度,所以考虑使用分治法,但将复杂度降为 O(nlogn) 还需要一些优化。 (关于运行时间的递归式为 T(n) = 2T(n2\frac n2)
【解题报告】最近点对问题 算法设计与分析 分治算法 openjudge
问题描述: 设平面上有N个点,求最近的两个点之间的距离(欧氏距离)。 解题思路: 典型的用分治思想来解决的问题。 如果采用简单暴力的方法,那么容易得出复杂度为O(n^2), 而采用分治的方法,将所有的点划分为两部分,分别解两部分内部的最短距离, 再考虑交叉部分的情况。由于距离的限制每个点只需要判断常数次。(可以参看《算法设计与分析》上的讲解,不具体展开) 如果每次找出交叉部分,然后直接...
自定义窗口
自定义窗口比较简单,但是有点问题,麻烦各位给看下,能否改好
求最近点对算法分析
本文引自  http://blog.csdn.net/lishuhuakai/article/details/9133961 问题描述:     在应用中,常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中,常需要了解其邻域中其他几何对象的信息。例如,在空中交通控制问题中,若将飞机作为空间中移动的一个点来看待,则具有最大碰撞危险的2架飞机,就是这
最近点对问题(分治思想的经典应用)
今天开始复习典型算法,首先回顾了分治算法的应用。一个经典的问题是求二维空间中最近点对。如果硬性用循环解决这个问题的话,当点的数量较大时,循环的次数会以O(n2)增加,所以这不是较好的解决方法。对于这种问题,可以通过将原问题不断划分为更小的子问题进而加以解决。在《数据结构、算法与应用-----c++语言描述》一书中给出了这一问题完备的分治递归解决方案。 算法过程如下: 1、如果点的数量n较小,则直
平面最近点对 洛谷1257 分治 c++
题目描述给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的。输入格式:第一行:n;2≤n≤10000接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。输出格式:仅一行,一个实数,表示最短距离,精确到小数点后面4位。说明本题爆搜即可Solution嗯,这么良心的说明已经少见了一直想刷的分治题。首先将点图排序、分成左右两半,分别
c++实现分治法最近点对算法
最近点对的算法是分治法的典型代表,所求的是平面上一堆点,求所有点对的距离的最小值,如果用暴力方法,其复杂度高达O(n*n)显然,效果太差,分治法的思想是将平面上的点分成左右两半,分别求左右两半的最小距离,然后取一个最小值,当然,最近点对还可能会有这样的情况,即一个点在左半边,一个点在右半边,这里,并不需要用暴力的方法求解所有的左边的和右边的最近点对,而是通过数学的一些证明将分治的其余代价降到O(n
最近二维点对
题目给定二维坐标系中的nn个点,求其中最近的点对。 测试输入 5 1 2 -2 3 2 -1 0 3 -3 0 测试输出 1.414 分析1如果将点的距离两两计算出来需要O(n2)O(n^2)的时间复杂度,显然不是最优方案。先考虑一维数组情况,如果数组已经排好序,则只需要再遍历一遍,找到相邻值的最小距离即可,时间复杂度只是O(nlog(n))O(nlog(n)),但是这种方法不能推广到
Java实现算法导论中最近点对问题分治法
最近点对问题:给定平面上的N个点,找出距离最近的两个点。分治法:              1 )如果数组长度(即点的个数,一般≤3)在一定范围内时直接求出最近点,蛮力求解,递归退出条件;              2)求出这些点的X坐标的中位数mid              3)以mid为界将所有点分为两组,分表放在表T1、T2中              4)将T1、T2表转换为数组
分治法求解最近点对问题
1:用一条竖直的线L将所有的点分成两等份   2:递归算出左半部分的最近两点距离d1,右半部分的最近两点距离d2,取d=min(d1,d2)    3:算出“一个在左半部分,另一个在右半部分”这样的点对的最短距离d3。 4:结果=min(d1,d2,d3)