836.Rectangle Overlap

836.Rectangle Overlap
难度:Easy
A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its bottom-left corner, and (x2, y2) are the coordinates of its top-right corner.
Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.
Given two (axis-aligned) rectangles, return whether they overlap.
1
Example 1:
2
​
3
Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
4
Output: true
5
Example 2:
6
​
7
Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
8
Output: false
9
Notes:
10
​
11
Both rectangles rec1 and rec2 are lists of 4 integers.
12
All coordinates in rectangles will be between -10^9 and 10^9.
Copied!
这里可以利用计算几何里的ToLeft测试，即判断一个点是否在一条线段的左边，主要是利用海伦公式，线段为有向线段。
对于不重叠的两个矩形，肯定对矩形的某一条边，四个顶点都在该条边的外侧，设矩形方向为逆时针，则四个点都在某一条边的右侧，则表示无重叠。
1
class Solution {
2
//To Left Test; line: px, py, qx,qy;point: sx,sy;
3
    //p.x * q.y - p.y* q.x + q.x * s.y - q.y * s.x + s.x * p.y - s.y * p.x;
4
bool toLeft(vector<int>rec1,int px, int py,int qx, int qy)
5
{
6
    vector<long int> tmp(4,0);
7
    int start=0;
8
    for(int i=0;i<3;i+=2)
9
        for(int j=1;j<4;j+=2)
10
        {
11
            int sx=rec1[i];
12
            int sy=rec1[j];
13
            tmp[start++] = (long)px*qy-(long)py*qx +(long)qx*sy -(long)qy*sx + (long)sx*py -(long)sy *px ;  
14
            }
15
   // cout<< px <<"   "<<py<<"   "<<qx<<"   "<<qy<<endl;
16
//   cout<<tmp[0] <<" "<< tmp[1] <<" "<<tmp[2] <<" "<< tmp[3]<<endl;
17
    if( tmp[0]<=0 && tmp[1]<=0 && tmp[2]<=0 && tmp[3]<=0) return true;
18
    return false;
19
​
20
}
21
public:
22
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
23
        
24
            return !(toLeft(rec1,rec2[0],rec2[1],rec2[2],rec2[1]) || toLeft(rec1,rec2[2],rec2[1],rec2[2],rec2[3]) || toLeft(rec1,rec2[2],rec2[3],rec2[0],rec2[3] ) || toLeft(rec1,rec2[0],rec2[3],rec2[0],rec2[1]));
25
        
26
    }
27
};
Copied!
执行用时 :4 ms, 在所有 C++ 提交中击败了75.38%的用户
内存消耗 :8.1 MB, 在所有 C++ 提交中击败了92.54%的用户
另一种方法，分别考虑x坐标和y坐标，如果有重叠，则两个矩形的x坐标的最大值与最小值的差应该小于两条矩形的x方向的边长之和。y轴同理。
1
class Solution {
2
​
3
public:
4
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
5
       return (long)max(rec2[2],rec1[2])-min(rec2[0],rec1[0]) < (long)rec2[2]-rec2[0]+ rec1[2]-rec1[0] && (long)max(rec2[3],rec1[3])-min(rec2[1],rec1[1]) < (long)rec2[3]-rec2[1]+rec1[3]-rec1[1] ;
6
        
7
    }
8
};
Copied!
执行用时 :4 ms, 在所有 C++ 提交中击败了75.38%的用户
内存消耗 :8.1 MB, 在所有 C++ 提交中击败了91.04%的用户

835,Image Overlap

840.Magic Squares In Grid

Last modified 5mo ago

Copy link