# Question

Formatted question description: https://leetcode.ca/all/391.html

 391	Perfect Rectangle

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point.
For example, a unit square is represented as [1,1,2,2]. (
coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [
[1,1,2,3],
[1,3,2,4],
[3,1,4,2],
[3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]
]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.



# Algorithm

The four vertices of all rectangles can only have the following three situations: blue, green, and red, where blue means there are no other rectangles around the vertex, a T-shaped green dot means two rectangles are next to each other, and a red dot means four rectangles are adjacent to each other. adjacent,

Then in a perfect rectangle, there can only be four blue points, which is a very important criterion. Let’s look at the four vertices of the rectangle again. Let’s label the vertices 1, 2, 4, and 8, in the order of bottom left, top left, top right, and bottom right. Why not 1, 2, 3, 4? Let’s pay attention to them. Binary 1(0001), 2(0010), 4(0100), 8(1000), which is convenient for us and OR operation.

Another criterion we need to know is that when a point is the lower left vertex of a certain rectangle, this point cannot be the lower left vertex of other rectangles. This condition must be true for these four vertices, then for each point If it is one of the four vertices of a certain rectangle, we record it. If it is the same vertex in other rectangles, then just return false directly, which reflects our mark as 1, 2, 4 , 8 benefits, we can check 1 bit by bit.

If the attributes of each point do not conflict, then we will verify whether the mask of each point is reasonable. Through the above analysis, we know that each point can only be one of the three cases of blue, green, and red, among which the blue case It is that there is only one 1 in the four bits of the mask, which are 1 (0001), 2 (0010), 4 (0100), 8 (1000), and there can only be four blue dots; then for the T-shaped green dot, mask There are two 1s in the four digits, then there are six situations, namely 12(1100), 10(1010), 9(1001), 6(0110), 5(0101), 3(0011); With the red dot, the four digits of the mask are all 1, and there is only one case of 15 (1111).

Then we can directly find the number of masks 1, 2, 4, and 8, or indirectly find the number of green dots and red dots to see if it is four. The last judgment condition is that the cumulative sum of each rectangular surface must be equal to the area of ​​the last large rectangle, then the area of ​​the large rectangle can be calculated by calculating the minimum lower left point and the maximum upper right point.

Java