父母B2悲剧，谁给分析一下情况 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Visa - 签证

父母B2悲剧，谁给分析一下情况

父母B2悲剧，谁给分析一下情况# Visa - 签证

b*72017-04-11 07:04

1 楼

Given a set of points (x,y) , find all pairs of points whose distance is
less than a given number, say, K.
这个题brute force：对每个点，求和其他点距离，O(N^2),不知道哪位大侠有高见啊
？请不吝赐教！万分感激！

t*22017-04-11 07:04

2 楼

父母以前来过三次
最近一次来的时候延期呆了一年
回国两年多了，又去签
签证官要了护照，别的什么也没要也没问就拒签了
我在怀疑是不是签证官看了护照上日期呆了一年
没有看到延期拘留批准信就以为他们在美国黑了半年？
我父母递护照的时候没有把延期批准信也递上去，
不知道这是不是就是拒签的原因
有过延期经历的能不能给分析一下
十分感谢！

s*i2017-04-11 07:04

3 楼

对啊，我也想问这题。面经里出现好几次，每次出现大家都说很old。就是没一个人给
个答案的。

【在 b******7 的大作中提到】

: Given a set of points (x,y) , find all pairs of points whose distance is
: less than a given number, say, K.
: 这个题brute force：对每个点，求和其他点距离，O(N^2),不知道哪位大侠有高见啊
: ？请不吝赐教！万分感激！

z*e2017-04-11 07:04

4 楼

我觉得是延期的问题。

a*s2017-04-11 07:04

5 楼

这个用quad tree解最好, 复杂度是相对于结果大小来说linear的

B*y2017-04-11 07:04

6 楼

我妈妈4年前来美,延期过一次。去年办的B1/B2签证,给她10年多次往返的。
只要不是来美太频繁,多次延期,让移民官觉得申请人有长期逗留美国的倾向。应该没有
问题。
建议,你父母分开去签证,申请来美停留时间写短一些,三,四个月。资金和国内关系多强
调,例如国内的家人,房产和退休金。
希望老人家签证顺利!

b*a2017-04-11 07:04

7 楼

sort the data, then a binary search?

a*92017-04-11 07:04

8 楼

等多久再签合适呢？我妈妈也是同样情况。

【在 B**********y 的大作中提到】

: 我妈妈4年前来美,延期过一次。去年办的B1/B2签证,给她10年多次往返的。
: 只要不是来美太频繁,多次延期,让移民官觉得申请人有长期逗留美国的倾向。应该没有
: 问题。
: 建议,你父母分开去签证,申请来美停留时间写短一些,三,四个月。资金和国内关系多强
: 调,例如国内的家人,房产和退休金。
: 希望老人家签证顺利!

g*y2017-04-11 07:04

9 楼

我觉得应该也能用closest pair的思路来做吧
我感觉quadtree的思路就是closest pair的思路的二维版

【在 a**********s 的大作中提到】

: 这个用quad tree解最好, 复杂度是相对于结果大小来说linear的

B*y2017-04-11 07:04

10 楼

这边的同学如果需要父母来帮忙照看孩子，延期过的。
最好隔一年吧，还有父母自己的资金能力也很重要；
反正就是证明申请人不差钱，邀请方不差钱，
来美国就是各种撒钱的。
他们喜欢这样的旅游者，你写邀请信的时候可以强调这点啊。

【在 a*******9 的大作中提到】

: 等多久再签合适呢？我妈妈也是同样情况。

a*h2017-04-11 07:04

11 楼

KD-tree is also able to find the solution.

b*72017-04-11 07:04

12 楼

不太懂，哪位能讲讲基本思路吗？

b*72017-04-11 07:04

13 楼

不太懂，哪位能讲讲基本思路吗？

a*r2017-04-11 07:04

14 楼

输出结果已经是N＊N的了，怎么可能更快。

m*f2017-04-11 07:04

15 楼

我详细说说吧，就是closest pair的思路
1. 在x轴上排序
2. 取中点x_middle把点分成左半边和右半边
3. 递归寻找左半边和右半边距离小于k得pair
4. 同时还有一边在左，一边在右的pair,
5. 3+4 = all answer
其他都是O(nlogn)没问题，第四步如果强解一样是o(n^2), 但是因为有条件是小于k,
那么只要考虑 x > x_middle-k 的左边点和 x < x_middle +k 的右边点即可，
并且对某个x_left, 只需考虑
x_middle < x_right < x_middle + k - (x_middle-x_left)
的右边点，可知是O(n).
应该没错把

n*r2017-04-11 07:04

16 楼

没觉得x轴上排序会有什么用
如果k等于最远两点间的距离
那么找出最远的两个点已经是0（N^2）复杂度了

,

【在 m*****f 的大作中提到】

: 我详细说说吧，就是closest pair的思路
: 1. 在x轴上排序
: 2. 取中点x_middle把点分成左半边和右半边
: 3. 递归寻找左半边和右半边距离小于k得pair
: 4. 同时还有一边在左，一边在右的pair,
: 5. 3+4 = all answer
: 其他都是O(nlogn)没问题，第四步如果强解一样是o(n^2), 但是因为有条件是小于k,
: 那么只要考虑 x > x_middle-k 的左边点和 x < x_middle +k 的右边点即可，
: 并且对某个x_left, 只需考虑
: x_middle < x_right < x_middle + k - (x_middle-x_left)

f*r2017-04-11 07:04

17 楼

这题问的有问题吧. 如果让你输出all pairs of points whose distance is
less than a given number K. 显然是O(N^2).
是不是应该问find K pairs of points with smallest distance. 这个有比O(N^2)好
的算法.

【在 b******7 的大作中提到】