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最大,而且是距离最远的点,就是要找的点
一年多之前 回复
wb_it_man
wb_it_man 第三步找右边X最大和Y最大的,但是只有X和Y同时最大才是最大的,这里应该怎么办?
一年多之前 回复
wb_it_man
wb_it_man   2016.05.06 18:40

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

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!