a********r
发帖数: 218 | 1 给一个list of points: a1(x1,y1), a2(x2, y2), ....找出其中相距最远的两个点，
有O(N)解法吗？ |
s******7
发帖数: 1758 | 2 真要遇到就跪吧
convex hull algorithms |
b*****t
发帖数: 296 | 3 以原点为坐标，算出每个点到原点的距离，找出最小的两个点，就是了。三角形两边之
和大于第三边。两边之和最小，就位所求。 |
r*g
发帖数: 186 | 4 先生成convex hull
然后考虑边界点的两两距离
convex hall生成算法是O(nlogn)
然后在convex hull上寻找两两最长点 复杂度是O(nlogn)
合计复杂度O(nlogn)
【在 a********r 的大作中提到】
: 给一个list of points: a1(x1,y1), a2(x2, y2), ....找出其中相距最远的两个点，
: 有O(N)解法吗？
|
b*****t
发帖数: 296 | 5 sorry，看成最小了，如果要最远，找最大的两个值就是了。 |
y*******3
发帖数: 158 | 6 感觉换成最大的话，两边之和大于第三边……不能保证最大的两个点的第三边也是最长
吧？
【在 b*****t 的大作中提到】
: sorry，看成最小了，如果要最远，找最大的两个值就是了。
|
p*********g
发帖数: 116 | 7 你的方法，最大最小，都求不出。
你画画就知道了。
【在 b*****t 的大作中提到】
: sorry，看成最小了，如果要最远，找最大的两个值就是了。
|
r*g
发帖数: 186 | 8 I think so
【在 p*********g 的大作中提到】
: 你的方法，最大最小，都求不出。
: 你画画就知道了。
|
v********o
发帖数: 67 | 9 convex hull能理解，后一步怎么在NlogN时间里找到hull上最远的两点？最坏情况下所
有点都在hull上
【在 r*g 的大作中提到】
: 先生成convex hull
: 然后考虑边界点的两两距离
: convex hall生成算法是O(nlogn)
: 然后在convex hull上寻找两两最长点 复杂度是O(nlogn)
: 合计复杂度O(nlogn)
|
x********o
发帖数: 25 | 10 对每个点找离它最远的是logn。
因为是convex hull，距离变化是一个严格凸函数。2分查找的时候check相邻的三点是
否满足两边的小于中间，如果是则返回，不是的话就接着2分。
convex hull能理解，后一步怎么在NlogN时间里找到hull上最远的两点？最坏情况下所
有点都在hull上
【在 v********o 的大作中提到】
: convex hull能理解，后一步怎么在NlogN时间里找到hull上最远的两点？最坏情况下所
: 有点都在hull上
|
l*********u
发帖数: 19053 | 11 用原点(0,0)好象不行，用(average X,average Y)做中心点，应该可以。
【在 b*****t 的大作中提到】
: sorry，看成最小了，如果要最远，找最大的两个值就是了。
|
v********o
发帖数: 67 | 12 这个convex hull定义不是这样的吧，你看(0，0)(1，1)(1.1,0)(1,-1)也是convex
hull，但其余三点(0，0)的距离不是两边小于中间啊
【在 x********o 的大作中提到】
: 对每个点找离它最远的是logn。
: 因为是convex hull，距离变化是一个严格凸函数。2分查找的时候check相邻的三点是
: 否满足两边的小于中间，如果是则返回，不是的话就接着2分。
:
: convex hull能理解，后一步怎么在NlogN时间里找到hull上最远的两点？最坏情况下所
: 有点都在hull上
|
b***e
发帖数: 1419 | 13 错。考虑一个1/4圆，一个顶点在圆心，其它三个顶点在圆上0，45，90处。 现在加两
个顶点，在22.5和67.5处，但是半径略小，使其仍保持凸。
【在 x********o 的大作中提到】
: 对每个点找离它最远的是logn。
: 因为是convex hull，距离变化是一个严格凸函数。2分查找的时候check相邻的三点是
: 否满足两边的小于中间，如果是则返回，不是的话就接着2分。
:
: convex hull能理解，后一步怎么在NlogN时间里找到hull上最远的两点？最坏情况下所
: 有点都在hull上
|
