wb_it_man 2016-05-06 05:53 采纳率: 66.7%
浏览 1386
已采纳

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

问题:(最近点对问题)设平面上有两个不同的点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

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

  • 写回答

2条回答

  • tianlang_2008 2016-05-06 07:24
    关注

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥20 iqoo11 如何下载安装工程模式
  • ¥15 flask项目,怎么使用AJAX传数据库数据到echarts图表的data里,实现异步加载数据。
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题