leetcode 391. Perfect Rectangle 完美矩形+判断4个点能否组成一个长方形

矫情吗；* 2022-06-03 20:49 194阅读 0赞

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.

直接参考原文链接[本题题意][Link 1]

**做法十分简单，一个主要的判断依据就是一个完美的正方形的4个顶点出现1次，其余的点都是出现偶数次，只需要做一个遍历即可完成，最后使用面积判断即可，**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    
    /*
      这道题看起来十分麻烦，其实十分简单，就是一个要点：只有正方形的4个顶点出现一次，
      其余的都是出现偶数次（可能2次或者4次），最后使用面积多判断即可
    */
    class Solution 
    {
    public:
        bool isRectangleCover(vector<vector<int>>& a) 
        {
            int sum = 0;
            int x1 = a[0][0], y1 = a[0][1], x2 = a[0][2], y2 = a[0][3];
            map<string, int> mmp;
            for (vector<int> one : a)
            {
                sum += (one[2] - one[0])*(one[3] - one[1]);
                if (one[0] <= x1 && one[1] <= y1)
                {
                    x1 = one[0];
                    y1 = one[1];
                }
                if (one[2] >= x2 && one[3] >= y2)
                {
                    x2 = one[2];
                    y2 = one[3];
                }
    
                string s1 = to_string(one[0]) + "" + to_string(one[1]);
                if (mmp.find(s1) == mmp.end())
                    mmp[s1] = 1;
                else
                    mmp[s1] = (mmp[s1] + 1)%2;
    
                string s2 = to_string(one[0]) + "" + to_string(one[3]);
                if (mmp.find(s2) == mmp.end())
                    mmp[s2] = 1;
                else
                    mmp[s2] = (mmp[s2] + 1) % 2;
    
    
                string s3 = to_string(one[2]) + "" + to_string(one[1]);
                if (mmp.find(s3) == mmp.end())
                    mmp[s3] = 1;
                else
                    mmp[s3] = (mmp[s3] + 1) % 2;
    
                string s4 = to_string(one[2]) + "" + to_string(one[3]);
                if (mmp.find(s4) == mmp.end())
                    mmp[s4] = 1;
                else
                    mmp[s4] = (mmp[s4] + 1) % 2;
            }
    
            string s1 = to_string(x1) + "" + to_string(y1);
            string s2 = to_string(x1) + "" + to_string(y2);
            string s3 = to_string(x2) + "" + to_string(y1);
            string s4 = to_string(x2) + "" + to_string(y2);
            if (mmp[s1] != 1 || mmp[s2] != 1 || mmp[s3] != 1 || mmp[s4] != 1)
                return false;
            mmp.erase(s1);
            mmp.erase(s2);
            mmp.erase(s3);
            mmp.erase(s4);
            for (map<string, int>::iterator i = mmp.begin(); i != mmp.end(); i++)
            {
                if (i->second % 2 != 0)
                    return false;
            }
    
            return sum == (x2 - x1)*(y2 - y1);
        }
    };

[Link 1]: https://leetcode.com/problems/perfect-rectangle/description/