求助:
原题:VLSI databases commonly represent an integrated circuit as a list of rectangles. Assume that each rectangle is rectilinearly oriented (sides parallel to the x- and y-axis), so that a representation of a rectangle consists of its minimum and maximum x- and y-coordinates. Give an O(n lg n)-time algorithm to decide whether or not a set of rectangles so represented contains two rectangles that overlap. Your algorithm need not report all intersecting pairs, but it must report that an overlap exists if one rectangle entirely covers another, even if the boundary lines do not intersect. (Hint: Move a "sweep" line across the set of rectangles.)
我的翻译: n 个矩形,其边要么与x轴平行,要么与y轴平行。每个矩形的四个顶点的坐标都给出。
问: 这n个矩形中 有没有两个矩形有相互重叠的部分。(只用给出 有还是没有,不用求出有多少对)
要求 在 n log n 时间内完成。
(Hint: Move a "sweep" line across the set of rectangles.)--〉提示:将一个扫描线扫过整个矩形集(?)
如果只是一维的话,直接用树做就可以了。但问题是 现在是二维的, 连怎么构造树我都没有思路(关键是怎么有效的划分)
还有那个提示。。。。不明白什么意思。
只用给出文字表述的思路即可,或者请用c++代码,别的语言我不会......