问题:(最近点对问题)设平面上有两个不同的点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
想到这里不知道接下来该怎么办了
我是初学者,可能有些啰嗦,问题又不是很难,麻烦大家帮我解决一下,谢谢