这题咋做？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

这题咋做？

这题咋做？# JobHunting - 待字闺中

l*a2011-12-05 08:12

1 楼

deck of cards
put them randomly on the table.
two cards can only overlap with rectangle area.(cards must be Vertical/
horizontal to the edge of the table)
find the total area covered by those cards

v*a2011-12-05 08:12

2 楼

Given, cards with (X_S1, X_E1, Y_S1, Y_E1)
1) Discretization on all points O(N)
O(N)
2) Sort by X
O(N)
3) Cut into pieces using sorted X.
O(N)
4) Count each piece separately.
O(N)
5) Sum up all
Total O(N)

e*l2011-12-05 08:12

3 楼

area(Table) - sum_i (area(Card i)) + sum_{i,j>i} Overlap(Card i, Card j)

C*h2011-12-05 08:12

4 楼

2楼对，3楼错。

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

: deck of cards
: put them randomly on the table.
: two cards can only overlap with rectangle area.(cards must be Vertical/
: horizontal to the edge of the table)
: find the total area covered by those cards

b*e2011-12-05 08:12

5 楼

O(NlgN)

m*s2011-12-05 08:12

6 楼

segment tree, O(nlogn)

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

H*e2011-12-05 08:12

7 楼

没看懂。什么叫discretization on all points?

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

: Given, cards with (X_S1, X_E1, Y_S1, Y_E1)
: 1) Discretization on all points O(N)
: O(N)
: 2) Sort by X
: O(N)
: 3) Cut into pieces using sorted X.
: O(N)
: 4) Count each piece separately.
: O(N)
: 5) Sum up all