d***8
发帖数: 1552 | 1 题目和解法如下。 没看懂解法。
Question: Axis Aligned Rectangles
Describe an algorithm that takes an unsorted array of axis‐aligned
rectangles and returns any pair of rectangles that overlaps, if there is such
a pair.
Axis‐aligned means that all the rectangle sides are either parallel or
perpendicular to the x‐ and y‐axis. You can assume that each rectangle
object has two variables in it: the x‐y coordinates of the upper‐left corner
and the bottom‐right corner.
Good Answer: Create a sorted array of the x coordinates of the left and
right edges of the rectangles. Then, use a "scanline" to move from left to
right through the rectangles. Keep a binary search tree containing the y
coordinates of the top and bottom edges of the rectangles that overlap the
scanline. For each element of the array, check whether it is a left or right
edge. If it is a right edge, remove the corresponding top and bottom edges
from the BST. If it is a left edge, search the BST for rectangles that overlap
the current rectangle; if there is one, return the overlap.
Then, add the y coordinates of the top and bottom edges of the rectangle to
the BST. The search takes O(n log n) time, since it takes O(n log n) time to
sort the rectangles and each of the 2n iterations takes O(log n) time. | i****d
发帖数: 35 | 2 印象中要用到range search
就是去BST里面找的时候
不然分析不出来O(nlgn)的 复杂度
such
corner
【在 d***8 的大作中提到】
: 题目和解法如下。 没看懂解法。
: Question: Axis Aligned Rectangles
: Describe an algorithm that takes an unsorted array of axis‐aligned
: rectangles and returns any pair of rectangles that overlaps, if there is such
: a pair.
: Axis‐aligned means that all the rectangle sides are either parallel or
: perpendicular to the x‐ and y‐axis. You can assume that each rectangle
: object has two variables in it: the x‐y coordinates of the upper‐left corner
: and the bottom‐right corner.
: Good Answer: Create a sorted array of the x coordinates of the left and
| P********l
发帖数: 452 | | D*********y
发帖数: 876 | 4 先把x方向左右两条边都sort一下，O(nlgn)
然后用以下的判断：
bool overlap(Rect a, Rect b) {
return ( a.ul.x <= b.lr.x &&
a.ul.y >= b.lr.y &&
a.lr.x >= b.ul.x &&
a.lr.y <= b.ul.y );
}
其中ul是upper left，lr是lower right
找满足a.ul.x <= b.lr.x和a.lr.x >= b.ul.x的
然后把满足条件的矩形的y方向两条边，加上要比较的矩形本身，sort一下
找到满足a.ul.y >= b.lr.y和a.lr.y <= b.ul.y |
|
