l*****a
发帖数: 14598 | 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***a
发帖数: 365 | 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***l
发帖数: 710 | 3 area(Table) - sum_i (area(Card i)) + sum_{i,j>i} Overlap(Card i, Card j) |
C*********h
发帖数: 74 | 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******e
发帖数: 52 | |
m******s
发帖数: 165 | 6 segment tree, O(nlogn)
【在 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
|
H***e
发帖数: 476 | 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
|
a********m
发帖数: 15480 | 8 不可能O(n)吧。
【在 C*********h 的大作中提到】
: 2楼对，3楼错。
|
H***e
发帖数: 476 | 9 这题谁能给个确切的解法么？似乎是经典题？
【在 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
|
z******t
发帖数: 59 | 10 既然有sort，怎么能是O(N)？
【在 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
|
z******t
发帖数: 59 | 11 Share a blog about this issue:
http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangle
It has detailed analysis and solution there. |
