J*Y
发帖数: 81 | 1 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‐alignedmeans 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. |
P*******U
发帖数: 203 | 2 判断相交有4种case，比较麻烦，不如直接判断不相交，很trivial。如果判断不相交的
函数返回false，那就是香蕉了 |
b***u
发帖数: 12010 | 3 我也见到这题了。出题的真缺德啊。
corner.
【在 J*Y 的大作中提到】
: 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‐alignedmeans 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.
|
l***i
发帖数: 1309 | 4 sweep line algorithm can do O(nlogn), or you can brute force to try all O(n^
2) pairs to check intersection. |
H***e
发帖数: 476 | |
