[面试]——用一行代码判断两矩形是否相交

typedef struct
{
    int left;
                // leftmost: 最左
    int top;
                // topmost: 最上

    int right;
                // rightmost: 最右
    int bottom;
                // bottommost: 最下

                // 其实两个点的组合，表达的是边界的概念
                // 分别为：
                // 左边界，右边界
                // 上边界，下边界
} Rect;

bool isRectOverlap(const RECT& r1, const RECT& r2)
{
    return !( ((r1.right < r2.left) || (r1.bottom > r2.top)) || 
              ((r2.right < r1.left) || (r2.bottom > r1.top)) 
            )
}
           

“两矩形相交”的对立事件（“两矩形不相交”比较容易表达（包含的情况数较少），最后对对立事件取非即可:

比如两矩形分别为r1和r2：

则两者不相交的情况为：r1在r2的左侧或上侧（同理，r2在r1的左侧或上侧），这里就要用到C结构体提供的界的概念了，也即r1的最右在r2最左的左侧，r1的最小在r2的最上的上侧。

((r1.right < r2.left) || (r1.bottom > r2.top))

((r2.right < r1.left) || (r2.bottom > r1.top))

不妨我们再对解决本题的思路“对立事件”的含义略作说明：

对立事件（Complementary event，直译为互补事件）

P(A c )=1−P(A) 

更像是常说的“非此即彼”，也即整个样本空间（sample space）中，事件 P(A)  与其对立事件 P(A c )  ，构成全部样本空间，放在本例也即，样本空间为：两矩形在平面上的组合形态，事件为：相交，则其对立事件自然为：不相交。

注意，正如

typedef struct rect

的四个成员变量所限制的那样，本文无法解决平面中不规则放置的矩形之间的关系。

References

[1] 判断两个矩形是否相交的方法