# 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.

```
Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true
Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false
Notes:

Both rectangles rec1 and rec2 are lists of 4 integers.
All coordinates in rectangles will be between -10^9 and 10^9.
```

这里可以利用计算几何里的ToLeft测试，即判断一个点是否在一条线段的左边，主要是利用海伦公式，线段为有向线段。\
对于不重叠的两个矩形，肯定对矩形的某一条边，四个顶点都在该条边的外侧，设矩形方向为逆时针，则四个点都在某一条边的右侧，则表示无重叠。

```
class Solution {
//To Left Test; line: px, py, qx,qy;point: sx,sy;
    //p.x * q.y - p.y* q.x + q.x * s.y - q.y * s.x + s.x * p.y - s.y * p.x;
bool toLeft(vector<int>rec1,int px, int py,int qx, int qy)
{
    vector<long int> tmp(4,0);
    int start=0;
    for(int i=0;i<3;i+=2)
        for(int j=1;j<4;j+=2)
        {
            int sx=rec1[i];
            int sy=rec1[j];
            tmp[start++] = (long)px*qy-(long)py*qx +(long)qx*sy -(long)qy*sx + (long)sx*py -(long)sy *px ;  
            }
   // cout<< px <<"   "<<py<<"   "<<qx<<"   "<<qy<<endl;
//   cout<<tmp[0] <<" "<< tmp[1] <<" "<<tmp[2] <<" "<< tmp[3]<<endl;
    if( tmp[0]<=0 && tmp[1]<=0 && tmp[2]<=0 && tmp[3]<=0) return true;
    return false;

}
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        
            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]));
        
    }
};
```

> 执行用时 :4 ms, 在所有 C++ 提交中击败了75.38%的用户\
> 内存消耗 :8.1 MB, 在所有 C++ 提交中击败了92.54%的用户

另一种方法，分别考虑x坐标和y坐标，如果有重叠，则两个矩形的x坐标的最大值与最小值的差应该小于两条矩形的x方向的边长之和。y轴同理。

```
class Solution {

public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
       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] ;
        
    }
};
```

> 执行用时 :4 ms, 在所有 C++ 提交中击败了75.38%的用户\
> 内存消耗 :8.1 MB, 在所有 C++ 提交中击败了91.04%的用户


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/836.rectangle_overlap.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.