完美矩形

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-rectangle

题目描述:

给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。
如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。

示例 1：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
输出：true
解释：5 个矩形一起可以精确地覆盖一个矩形区域。

示例 2：

输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
输出：false
解释：两个矩形之间有间隔，无法覆盖成一个矩形。

示例 3：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]
输出：false
解释：图形顶端留有空缺，无法覆盖成一个矩形。

示例 4：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
输出：false
解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

代码实现:

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int x = 10001, y = 10001, a = -10001, b = -10001;
        long s = 0;
        Map<String, Integer> cnts = new HashMap<>();
        for(int[] r: rectangles){
            x = Math.min(x, r[0]);
            y = Math.min(y, r[1]);
            a = Math.max(a, r[2]);
            b = Math.max(b, r[3]);
            s += (r[3] - r[1]) * (r[2] - r[0]);
            String p1 = point(r[0], r[1]), p2 = point(r[0],r[3]), p3 = point(r[2], r[1]), p4 = point(r[2],r[3]);
            cnts.put(p1, cnts.getOrDefault(p1, 0) + 1);
            cnts.put(p2, cnts.getOrDefault(p2, 0) + 1);
            cnts.put(p3, cnts.getOrDefault(p3, 0) + 1);
            cnts.put(p4, cnts.getOrDefault(p4, 0) + 1);
        }
        if(s != (a - x) * (b - y))
            return false;
        Set<String> points = new HashSet<>(){};
        points.add(point(x, y)); 
        points.add(point(x, b));
        points.add(point(a, y));
        points.add(point(a, b));
        for(String p:points){
            if(!cnts.containsKey(p) || cnts.get(p) != 1)
                return false;
        }
        for(String p:cnts.keySet()){
            if(!points.contains(p)){
                int v = cnts.get(p);
                if(v > 4 || v % 2 != 0)
                    return false;
            }
        }
        return true;
    }

    private String point(int x, int y){
        return String.format("%d,%d",x,y);
    }
}