EB1的三年research 经历# Immigration - 落地生根a*r2013-07-17 07:071 楼给一个list of points: a1(x1,y1), a2(x2, y2), ....找出其中相距最远的两个点,有O(N)解法吗?
x*g2013-07-17 07:074 楼我让phd老板除了推荐信又写了一封信证明研究经历。去。【在 h****d 的大作中提到】: phd毕业一年,申请EB1B的话,证明三年research 经验的话,需要把PhD研究也算上去。: evidence除了老板推荐信,还有什么可以证明?
r*g2013-07-17 07:077 楼先生成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)解法吗?
y*32013-07-17 07:079 楼感觉换成最大的话,两边之和大于第三边……不能保证最大的两个点的第三边也是最长吧?【在 b*****t 的大作中提到】: sorry,看成最小了,如果要最远,找最大的两个值就是了。
v*o2013-07-17 07:0712 楼convex hull能理解,后一步怎么在NlogN时间里找到hull上最远的两点?最坏情况下所有点都在hull上【在 r*g 的大作中提到】: 先生成convex hull: 然后考虑边界点的两两距离: convex hall生成算法是O(nlogn): 然后在convex hull上寻找两两最长点 复杂度是O(nlogn): 合计复杂度O(nlogn)
x*o2013-07-17 07:0713 楼对每个点找离它最远的是logn。因为是convex hull,距离变化是一个严格凸函数。2分查找的时候check相邻的三点是否满足两边的小于中间,如果是则返回,不是的话就接着2分。convex hull能理解,后一步怎么在NlogN时间里找到hull上最远的两点?最坏情况下所有点都在hull上【在 v********o 的大作中提到】: convex hull能理解,后一步怎么在NlogN时间里找到hull上最远的两点?最坏情况下所: 有点都在hull上
l*u2013-07-17 07:0714 楼用原点(0,0)好象不行,用(average X,average Y)做中心点,应该可以。【在 b*****t 的大作中提到】: sorry,看成最小了,如果要最远,找最大的两个值就是了。
v*o2013-07-17 07:0715 楼这个convex hull定义不是这样的吧,你看(0,0)(1,1)(1.1,0)(1,-1)也是convexhull,但其余三点(0,0)的距离不是两边小于中间啊【在 x********o 的大作中提到】: 对每个点找离它最远的是logn。: 因为是convex hull,距离变化是一个严格凸函数。2分查找的时候check相邻的三点是: 否满足两边的小于中间,如果是则返回,不是的话就接着2分。: : convex hull能理解,后一步怎么在NlogN时间里找到hull上最远的两点?最坏情况下所: 有点都在hull上
b*e2013-07-17 07:0716 楼错。考虑一个1/4圆,一个顶点在圆心,其它三个顶点在圆上0,45,90处。 现在加两个顶点,在22.5和67.5处,但是半径略小,使其仍保持凸。【在 x********o 的大作中提到】: 对每个点找离它最远的是logn。: 因为是convex hull,距离变化是一个严格凸函数。2分查找的时候check相邻的三点是: 否满足两边的小于中间,如果是则返回,不是的话就接着2分。: : convex hull能理解,后一步怎么在NlogN时间里找到hull上最远的两点?最坏情况下所: 有点都在hull上