坐标均为整数,矩形可视为半开区域 [x1,x2)×[y1,y2)。查询区域内每个单位格 (x,y)(x∈[qx1,qx2),y∈[qy1,qy2))至多对应一个最上层控件:从大编号到小编号扫描,第一个覆盖该格的矩形即为该格可见控件。
收集所有出现过的顶层编号,再按降序输出。相切(无单位格)自然不会被计入,符合「相切不算相交」。
常见假解:
视画布为一个左上角为 (0, 0) 的直角坐标系,现给定一组矩形 UI 控件 rects,编号为 i 的控件 rects[i] = [x1, y1, x2, y2],左上角坐标为 (x1, y1)、右下角坐标为 (x2, y2),根据输入顺序依次绘制在画布上(后绘制的矩形在上层)。
给定一个查询的矩形区域 queryRect(格式同 UI 控件),请找出所有在查询区域内可见的 UI 控件,并返回这些控件的编号列表(编号降序),可能为空列表 []。一个 UI 控件可见的条件是:
对照样例1的输入数据,如下图所示:

给出的查询区域为 [2, 2, 6, 3],虽然橙色控件被上层的黄色控件覆盖了一部分区域,但是在查询区域内橙色控件仍然有部分区域未被覆盖,在查询区域内黄色控件未被任何控件覆盖。所以,橙色控件、黄色控件都属于可见的 UI 控件。
第一个参数为 rects,1 <= rects.length <= 100
第二个参数为 queryRect
0 <= x1 < x2 <= 100,0 <= y1 < y2 <= 100,且都为整数。
可见控件的编号列表(按编号降序)
输入:
[[0, 0, 4, 5], [1, 1, 3, 3], [2, 2, 5, 4], [4, 2, 5, 3], [5, 3, 6, 4]]
[2, 2, 6, 3]
输出:
[3, 2]
解释:
参考题目中的图:
按照绘制顺序,先绘制 rects[0]=[0, 0, 4, 5],再绘制 rects[1]、rects[2]……
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.