矩形重叠
矩形以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。
如果相交的面积为正,则称两矩形重叠。需要明确的是,只在角或边接触的两个矩形不构成重叠。
给出两个矩形,判断它们是否重叠并返回结果。
示例 1:
输入:rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出:true
示例 2:
输入:rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出:false
提示:
两个矩形 rec1 和 rec2 都以含有四个整数的列表的形式给出。
矩形中的所有坐标都处于 -109 和 109 之间。
x 轴默认指向右,y 轴默认指向上。
你可以仅考虑矩形是正放的情况。
自我解答:
又是一次吐了一口老血的解答。从区间角度着手,看似很容易处理,但当我尝试去考虑所有重叠的情况后,
发现情况真的有点多。代码写了30多行后,几个测试案例通过了,一提交就发现还有没有考虑到的情况,
若再因此去修改代码,只会让代码变得更臭更长。思前想后,没有别的思路了。
力扣题解:
值得庆幸的是,力扣题解也是从区间角度着手的,但不是去找所有重叠情况,而是找所有不重叠情况,然后取反!!!
重叠的情况太多了,不重叠的情况便少多了,取反操作,便巧妙地解决了这个问题。
这又是一次数学逆向思维的运用,如果需要考虑的情况特别多,可以考虑对立面的例子,如果对立面情况很少的话,
那就直接取反就行了。
def is_rectangle_overlap(rec1: List[int], rec2: List[int]) -> bool:
ax1, ay1, ax2, ay2 = rec1
bx1, by1, bx2, by2 = rec2
return not (bx1 >= ax2 or by2 <= ay1 or bx2 <= ax1 or by1 >= ay2)