坐标均为整数,矩形可视为半开区域 [x1,x2)×[y1,y2)。查询区域内每个单位格 (x,y)(x∈[qx1,qx2),y∈[qy1,qy2))至多对应一个最上层控件:从大编号到小编号扫描,第一个覆盖该格的矩形即为该格可见控件。
收集所有出现过的顶层编号,再按降序输出。相切(无单位格)自然不会被计入,符合「相切不算相交」。
常见假解:
平面上左上角为 (0,0)。给定矩形数组 rects,rects[i]=[x1,y1,x2,y2] 表示编号为 i 的矩形(左上 (x1,y1),右下 (x2,y2))。按数组下标从小到大依次叠放,下标更大者在上层。
再给定查询矩形 queryRect(格式相同)。求查询区域内可见矩形的编号列表(编号降序;可为空 [])。编号 i 可见当且仅当:
样例1 对应下图(虚线框为查询矩形):

图中查询为 [2,2,6,3]:编号 2(橙色)在查询带内仍有未遮挡部分;编号 3(黄色)在查询带内处于顶层。二者均可见。
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]
说明:
与上图一致。编号 4 与查询不相交。编号 0,1,2,3 与查询相交,但 0,1 在相交区内被上层 2 完全盖住;2,3 仍有露出,降序为 [3,2]。
输入:
[[0, 0, 5, 5], [2, 2, 4, 4], [3, 3, 5, 5]]
[1, 1, 4, 4]
输出:
[2, 1, 0]
说明:
查询正方形内,三个矩形各自在某些单位格上成为顶层,故三个编号均可见。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.