esc to dismiss
x
Home / week-85 / 836

信息

题解

题目的矩形, 是靠 左下角/右上角 两个顶点确定的, 因此必然是垂直于X轴/Y轴的

思路1

排除法, 将没有交叠的情况枚举出来, 取反 

pub fn is_rectangle_overlap(rec1: Vec<i32>, rec2: Vec<i32>) -> bool {
    use std::convert::TryFrom;
    let [x1, y1, x2, y2] = <[i32; 4]>::try_from(rec1).ok().unwrap();
    let [a1, b1, a2, b2] = <[i32; 4]>::try_from(rec2).ok().unwrap();
    if x1 == x2 || y1 == y2 || a1 == a2 || b1 == b2 {
        return false;
    }
    // 排除法
    !(
        x1 >= a2 || // rec1 在 rec2 的右边
        x2 <= a1 || // rec1 在 rec2 的左边
        y1 >= b2 || // rec1 在 rec2 的上方
        y2 <= b1    // rec1 在 rec2 的下方
    )
}

思路2

如果有交叠, 投影到X轴的后, 两线段应该相交, 同理投影Y轴

假定两线段为 \([a, b]\) 和 \([c, d]\), 相交的情况有
(a, c, b, d)
(a, c, d, b)
(c, a, d, b)
(c, a, b, d)

汇总起来, 只要 min(b, d) > max(a, c) 即可 

pub fn is_rectangle_overlap(rec1: Vec<i32>, rec2: Vec<i32>) -> bool {
    use std::convert::TryFrom;
    use std::cmp::{min, max};
    let [x1, y1, x2, y2] = <[i32; 4]>::try_from(rec1).ok().unwrap();
    let [a1, b1, a2, b2] = <[i32; 4]>::try_from(rec2).ok().unwrap();

    min(x2, a2) > max(x1, a1) && min(y2, b2) > max(y1, b1)
}

Backlinks

Tags

x