首页 > 试题广场 >

VLSI数据库通常将一块集成电路表示成一组矩形,假设每个矩形

[问答题]
VLSI数据库通常将一块集成电路表示成一组矩形,假设每个矩形的边都平行于x轴或者y轴,这样可以用矩形的最小和最大的x轴与y轴坐标来表示一个矩形。请给出一个O(nlgn)时间的算法,来确定n个这种表示的矩形集合是否存在两个重叠的矩形。你的算法不一定要输出所有重叠的矩形,但对于一个矩形完全覆盖另一个(即使边界线不相交),一定能给出正确的判断。(提示:移动一条“扫描”线,穿过所有的矩形。)

这道题你会答吗?花几分钟告诉大家答案吧!