Leetcode 391. Perfect Rectangle

ゝ一世哀愁。 2022-07-17 03:29 38阅读 0赞

## 解题思想 ##

这道题是说给了一堆小矩形的坐标（左下角和右上角围成的），问其能否组合成一个完美的矩形（刚刚好，不多，不少，不交叉重复）。

核心思想就是:能够正好围成一个矩形的情况就是:  
有且只有:

*  最左下/最左上/最右下/最右上的四个点只出现过一次,其他肯定是出现两次和四次(保证完全覆盖)
 *  上面四个点围成的面积,正好等于所有子矩形的面积之和(保证不重复)

[Leetcode代码收录][Leetcode]，求粉求星星。

class Solution(object):
        def isRectangleCover(self, rectangles):
            """ :type rectangles: List[List[int]] :rtype: bool """
            def recordCorner(point):
                if point in corners:
                    corners[point] += 1
                else:
                    corners[point] = 1
    
            corners = {}
            area =  0
            left = min(x[0] for x in rectangles)
            bottom = min(x[1] for x in rectangles)
            right = max(x[2] for x in rectangles)
            top = max(x[3] for x in rectangles)
    
            for sub in rectangles:
                ax, ay, bx, by = sub[:]
                area += (bx-ax)*(by-ay)
                map(recordCorner, [(ax, ay), (bx, by), (ax, by), (bx, ay)])
    
            if area != (top-bottom)*(right-left): return False
    
            big_four = [(left,bottom),(right,top),(left,top),(right,bottom)]
    
            for bf in big_four:                         # check corners of big rectangle
                if bf not in corners or corners[bf] != 1:
                    return False
    
            for key in corners:                         # check existing "inner" points
                if corners[key]%2 and key not in big_four:
                    return False
    
            return True

[Leetcode]: https://github.com/Mr-Phoebe/ACM-ICPC/tree/master/OJ/Leetcode