请勿打扰2.0版 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

请勿打扰2.0版

请勿打扰2.0版# Joke - 肚皮舞运动

k*r2013-10-10 07:10

1 楼

从别处看来的，
给定N个点，每个点有(x,y)坐标，要找一个最小面积的矩形，使得它cover至少k个点.
这个题目输入是那N个坐标和参数k, 输出是最小面积矩形
这个题O(N)能不能搞定，还是必须要O(N^2). 哪位大牛谈谈

t*r2013-10-10 07:10

2 楼

听说本版有冰箱贴和实例，请教一下。

l*d2013-10-10 07:10

3 楼

www.trackitt.com/usa-immigration-trackers/i485-eb
有人发过这个么

f*i2013-10-10 07:10

4 楼

w*s2013-10-10 07:10

5 楼

积分图像
扫一遍可以获得积分图像
S(i,j)=从(0,0)到(i,j)的点的个数
之后，对于任意的矩形(i,j),(k,l)，都可以一步求得其中包含的点的个数
S2 = S(k,l) - S(k,j) - S(i,l) + S(i,j)
O(n^2)肯定可以搞定。

点.

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

: 从别处看来的，
: 给定N个点，每个点有(x,y)坐标，要找一个最小面积的矩形，使得它cover至少k个点.
: 这个题目输入是那N个坐标和参数k, 输出是最小面积矩形
: 这个题O(N)能不能搞定，还是必须要O(N^2). 哪位大牛谈谈

y*g2013-10-10 07:10

6 楼

推成功的也是因为本来就是155，只不过没暴露出来
跟110完全不是一个脉路的
155虽然也会贪玩，但capabilities体现出来的不会是110啊

k*r2013-10-10 07:10

7 楼

你这个解法在O(n^2)不一定找得到最优解，因为所要找到的矩形顶点，未必就在给定点
中。
比如给定三个点(0,0), (0,4), (4,0), k=3, 那么解答应该是(0,0), (4,4). 但(4,4)
这个点不在给定点中。
这样一来，如果用你的解法，就要try out all rectangles, 你要考虑可能的顶点数就
是O(N^2)个了，那你的矩形candidate数就是O(n^4)

P*e2013-10-10 07:10

8 楼

刷一刷智商测试题就行。
不还有专补智商的补习班么。

★ 发自iPhone App: ChineseWeb 1.0.2
★ 发自iPhone App: ChineseWeb 1.0.2

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

: 推成功的也是因为本来就是155，只不过没暴露出来
: 跟110完全不是一个脉路的
: 155虽然也会贪玩，但capabilities体现出来的不会是110啊

k*r2013-10-10 07:10

9 楼

另外题目中约束条件是至少含K个点，而不是刚好含K个点，所以题目的约束条件是一
个比较松弛的条件，按说可以用这减少时间复杂度的

y*g2013-10-10 07:10

10 楼

那不是155，而是告诉110前面有个160
155到160是不用被告诉的，顶多就是纠正一下

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

: 刷一刷智商测试题就行。
: 不还有专补智商的补习班么。
:
: ★ 发自iPhone App: ChineseWeb 1.0.2
: ★ 发自iPhone App: ChineseWeb 1.0.2

k*r2013-10-10 07:10

11 楼

另外题目中约束条件是至少含K个点，而不是刚好含K个点，所以题目的约束条件是一
个比较松弛的条件，按说可以用这减少时间复杂度的

k*m2013-10-10 07:10

12 楼

先举例，啥人是110，啥人是160+？

f*e2013-10-10 07:10

13 楼

for(int i = 0; i < rows; ++i){
for(int j = 0; j <= i; ++j){
对从j到i的rows使用蠕虫算法。
}
}
复杂度O(N^3)

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

: 另外题目中约束条件是至少含K个点，而不是刚好含K个点，所以题目的约束条件是一
: 个比较松弛的条件，按说可以用这减少时间复杂度的

l*g2013-10-10 07:10

14 楼

这个难道不是生下来就确定了的？？？

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

: 听说本版有冰箱贴和实例，请教一下。

s*g2013-10-10 07:10

15 楼

想到一个nlogn的算法：
先按照x value对n个点排序，然后对它们按照y value建segment tree。这样的话，对
第i到i+k-1个点，只需要O(1)找出x_max和x_min，需要O(logn)找出y_max和y_min。
这个方法假设了正方形的下边沿和x轴平行。如果没有这个constraint的话，可能更复
杂了

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

: 另外题目中约束条件是至少含K个点，而不是刚好含K个点，所以题目的约束条件是一
: 个比较松弛的条件，按说可以用这减少时间复杂度的

w*02013-10-10 07:10

16 楼

为啥要推160+？

c*02013-10-10 07:10

17 楼

记得数据结构课上讲过一种结构，专门解决这个问题的…

点.

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

r*g2013-10-10 07:10

18 楼

即使有，也是娃先长得慢后长得快，家长还以为是自己教育的功劳。

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

: 听说本版有冰箱贴和实例，请教一下。

k*r2013-10-10 07:10

19 楼

shicong，你的nlogn解法好像不能保证最优解吧，因为你的算法是对每k个x坐标连续的
点，算出覆盖这k个点的矩形最小面积。
但既然你没有遍历所有可能的k个点，就不能保证你漏掉的那些矩形candidate不含更优
的解啊。换句话说，最优解矩形含的那k个点，他们在x坐标未必连续啊

S*s2013-10-10 07:10

20 楼

卧推的话110就很牛了

f*e2013-10-10 07:10

21 楼

嗯，最小长方形有可能是扁的，not bounded by ymin and ymax。

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

: shicong，你的nlogn解法好像不能保证最优解吧，因为你的算法是对每k个x坐标连续的
: 点，算出覆盖这k个点的矩形最小面积。
: 但既然你没有遍历所有可能的k个点，就不能保证你漏掉的那些矩形candidate不含更优
: 的解啊。换句话说，最优解矩形含的那k个点，他们在x坐标未必连续啊

q*i2013-10-10 07:10

22 楼

我觉得孩子自己得有self motivation吧。有了这个什么都不难。

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

: 听说本版有冰箱贴和实例，请教一下。

w*s2013-10-10 07:10

23 楼

大于n^2, 小于n^3。
对从(k,j)开始的点，遍历(k+n), (j+m)，如果遇到>k的时候，可以break，对于k+n,
寻找最小的m，也可以用二分查找法。

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

: 你这个解法在O(n^2)不一定找得到最优解，因为所要找到的矩形顶点，未必就在给定点
: 中。
: 比如给定三个点(0,0), (0,4), (4,0), k=3, 那么解答应该是(0,0), (4,4). 但(4,4)
: 这个点不在给定点中。
: 这样一来，如果用你的解法，就要try out all rectangles, 你要考虑可能的顶点数就
: 是O(N^2)个了，那你的矩形candidate数就是O(n^4)

t*r2013-10-10 07:10

24 楼

普通 teen 娃的 self motivation 是打游戏看韩剧啊。

【在 q****i 的大作中提到】

: 我觉得孩子自己得有self motivation吧。有了这个什么都不难。

l*z2013-10-10 07:10

25 楼

正确性好像有问题

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

: 想到一个nlogn的算法：
: 先按照x value对n个点排序，然后对它们按照y value建segment tree。这样的话，对
: 第i到i+k-1个点，只需要O(1)找出x_max和x_min，需要O(logn)找出y_max和y_min。
: 这个方法假设了正方形的下边沿和x轴平行。如果没有这个constraint的话，可能更复
: 杂了

t*22013-10-10 07:10

26 楼

SELF MOTIVATION最高境界是对外界本能的热爱和不屈不挠的探求精神。
次一等是热爱努力勤奋带来的成就感。
再其次是无法接受不努力不勤奋带来的后果。

l*z2013-10-10 07:10

27 楼

网格边长都是2N吧，这样最终复杂度还是O(n^2)

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

q*i2013-10-10 07:10

28 楼

你别给他这个环境啊。比如我家完全没有电脑和电视给娃。我还叫娃管我，我一看手机
娃就很严肃的对我说，会看坏眼睛。她管我。我看到好的视频也和娃分享，但是她做了
＂老师＂＂教练＂以后自己的自控能力非常好。。。

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

: 普通 teen 娃的 self motivation 是打游戏看韩剧啊。

s*g2013-10-10 07:10

29 楼

确实考虑不周了...

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

q*i2013-10-10 07:10

30 楼

人一旦习惯了积极的生活，要变成养猪也是同样难受的。我有个很沉沦的闺蜜有几天不
在家，她妈妈叫我过去吃饭。就像对她闺女一样对我，丰盛而健康的午饭后叫我像她女
儿一样去睡觉，我没有午觉的习惯，在床上翻来覆去睡不着非常痛苦，就这样在她家关
了我一个下午，然后吃丰盛的晚饭。我那天那个难受啊。。。。。再不去了。。。

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

: SELF MOTIVATION最高境界是对外界本能的热爱和不屈不挠的探求精神。
: 次一等是热爱努力勤奋带来的成就感。
: 再其次是无法接受不努力不勤奋带来的后果。

g*y2013-10-10 07:10

31 楼

Can the rectangle be rotated?

点.

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

q*i2013-10-10 07:10

32 楼

哦，还有，老师和你的表扬非常重要，就是要做娃的粉丝。我认识一个超级妈妈，大女
儿是当地最好学校考进去的第二，二女儿是首席小提琴手，其他什么样样都好。我告诉
她我家娃不愿意去上课，一换老师就quit课。她就告诉我，她和我正好相反，每次娃去
上课都特别早去，和老师搞好关系，老师特别欣赏她家娃，她娃也因此有无限的动力。
跳舞什么都拿奖。就是因为妈妈给孩子的动力。motivation来自于娃参与那些活动时候
得到的成就和表扬。

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

: 普通 teen 娃的 self motivation 是打游戏看韩剧啊。

l*82013-10-10 07:10

33 楼

two-d tree吧

点.

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

t*r2013-10-10 07:10

34 楼

teen 不是五岁娃。当然我目前能对付这个电视和游戏时间了。

【在 q****i 的大作中提到】

: 你别给他这个环境啊。比如我家完全没有电脑和电视给娃。我还叫娃管我，我一看手机
: 娃就很严肃的对我说，会看坏眼睛。她管我。我看到好的视频也和娃分享，但是她做了
: ＂老师＂＂教练＂以后自己的自控能力非常好。。。

s*t2013-10-10 07:10

35 楼

二维线段树，建树O(x*y),query O(logn)
如果是rotate rectangle 或者坐标是double什么的，我就不知道了

q*i2013-10-10 07:10

36 楼

那就参见上贴super妈妈了，我家只有４岁娃，我说的那个super妈妈大娃高二小娃初中
好像。

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

: teen 不是五岁娃。当然我目前能对付这个电视和游戏时间了。

i*t2013-10-10 07:10

37 楼

How about this?
Create a data structure like range tree to efficiently search for the needed
points.
For each point, create a rectangle of area zero.
Then for each rectangle containing one point, enlarge the rectangle to
contain one more point that increase the area the least. So now there are at
most n-1 rectangles each containing two points.
Then for each rectangle with two points, enlarge it again by adding another
point that still minimizing the area of that rectangle.
Repeat this until each rectangle contains k points.
There are at most n-k+1 such rectangles. Return the one with the smallest
area.
Looks like the complexity is O(knlogn)

d*h2013-10-10 07:10

38 楼

她闺女是不是出去避难了？

【在 q****i 的大作中提到】

: 人一旦习惯了积极的生活，要变成养猪也是同样难受的。我有个很沉沦的闺蜜有几天不
: 在家，她妈妈叫我过去吃饭。就像对她闺女一样对我，丰盛而健康的午饭后叫我像她女
: 儿一样去睡觉，我没有午觉的习惯，在床上翻来覆去睡不着非常痛苦，就这样在她家关
: 了我一个下午，然后吃丰盛的晚饭。我那天那个难受啊。。。。。再不去了。。。

i*t2013-10-10 07:10

39 楼

flg是什么？

h*62013-10-10 07:10

40 楼

是这个么
http://cisjournal.org/journalofcomputing/archive/vol3no6/vol3no

n*e2013-10-10 07:10

41 楼

包含两个点的为啥是n-1个？
难道不是 C(n,2) 个么？

needed
at
another

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

: How about this?
: Create a data structure like range tree to efficiently search for the needed
: points.
: For each point, create a rectangle of area zero.
: Then for each rectangle containing one point, enlarge the rectangle to
: contain one more point that increase the area the least. So now there are at
: most n-1 rectangles each containing two points.
: Then for each rectangle with two points, enlarge it again by adding another
: point that still minimizing the area of that rectangle.
: Repeat this until each rectangle contains k points.

i*t2013-10-10 07:10

42 楼

是让面积最小的点。
每个点都可以找到另一个点让面积最小。

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

: 包含两个点的为啥是n-1个？
: 难道不是 C(n,2) 个么？
:
: needed
: at
: another

i*t2013-10-10 07:10

43 楼

我发现这个greedy algorithm也不能保证最优解。
比如说要从下面这6个点找4点
.
..

..
.

needed
at
another

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

i*t2013-10-10 07:10

44 楼

好像是。不过质量可能不是很好。
刚找到这篇可能好点
www.cccg.ca/proceedings/1996/cccg1996_0004.pdf

【在 h******6 的大作中提到】

: 是这个么
: http://cisjournal.org/journalofcomputing/archive/vol3no6/vol3no

D*12013-10-10 07:10

45 楼

不好意思，刚点成回复给作者了。您能给个O(N^2)的算法吗？

点.

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