city 的 thank you forward看电影有5% cash back? - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Money - 海外理财

city 的 thank you forward看电影有5% cash back?

city 的 thank you forward看电影有5% cash back?# Money - 海外理财

B*t2011-04-10 07:04

1 楼

二维平面上有一堆点，坐标都是整数
1. 寻找一个圆，使圆周上经过的点最多
有没有比O(N^3)更好的算法？
2. 给定圆的半径r，把这圆放在什么位置可以覆盖最多的点？
有没有比O(N^2logN)更好的算法？
3. 包含所有点的最小的圆的半径是多少？
我能想到的方法，从3个点开始，每次加一个点进去，并维持一个最小圆，直到所有的圆都加进去。这个的复杂度应该是O(N)。不过常数项比较大，还有其它的方法么？

p*y2011-04-10 07:04

2 楼

请问下city thank you forward卡看电影有5%的cash back, 那电影是不是有包括
broadway show呢?多谢啦

k*e2011-04-10 07:04

3 楼

几何题目太难了
我觉得被问到的可能性非常非常小

的圆都加进去。这个的复杂度应该是O(N)。不过常数项比较大，还有其它的方法么？

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

: 二维平面上有一堆点，坐标都是整数
: 1. 寻找一个圆，使圆周上经过的点最多
: 有没有比O(N^3)更好的算法？
: 2. 给定圆的半径r，把这圆放在什么位置可以覆盖最多的点？
: 有没有比O(N^2logN)更好的算法？
: 3. 包含所有点的最小的圆的半径是多少？
: 我能想到的方法，从3个点开始，每次加一个点进去，并维持一个最小圆，直到所有的圆都加进去。这个的复杂度应该是O(N)。不过常数项比较大，还有其它的方法么？

B*t2011-04-10 07:04

4 楼

hehe, the 1st one has been asked for several times. the interviewers seem to
look for a O(N^2) or even O(N) solution. but I just couldnot find an answer
yet.

【在 k***e 的大作中提到】

: 几何题目太难了
: 我觉得被问到的可能性非常非常小
:
: 的圆都加进去。这个的复杂度应该是O(N)。不过常数项比较大，还有其它的方法么？

k*e2011-04-10 07:04

5 楼

哪个公司？
应该是paper上解决的题目，谁有兴趣去找一下？
整点有什么用处？圆心可能不在整点上

to
answer

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

: hehe, the 1st one has been asked for several times. the interviewers seem to
: look for a O(N^2) or even O(N) solution. but I just couldnot find an answer
: yet.

B*t2011-04-10 07:04

6 楼

I don't know which company, the 1st problem is from the "Quant 版面". I
restrict integer coordinates for each points to make the problems easier.

【在 k***e 的大作中提到】

: 哪个公司？
: 应该是paper上解决的题目，谁有兴趣去找一下？
: 整点有什么用处？圆心可能不在整点上
:
: to
: answer