trafficstars

文章链接点这里：如何判定完美矩形

评论礼仪见这里，违者直接拉黑。

Nov 16 '21 03:11 utterances-bot

这个题没做过类似题还真想不到

Nov 16 '21 03:11 lcfgrn

也就是说，当某一个点同时是 2 个或者 4 个小矩形的顶点时，该点最终不是顶点；

但如果2个矩形完全重合，那么这4个顶点全部同时是2个矩形的定点呢

Nov 17 '21 08:11 wangpeiming110

回复楼上，如果4个顶点全部同时是2个矩形的顶点，那么set最终为空

Nov 18 '21 09:11 Park-J-lab

@labuladong 其实，只要保证最后len(points) = 4 以及 actual_area = expected_area即可，无需再检查留下的 4 个顶点是否是完美矩形的顶点。因为只要len(points) = 4，那么说明留下的四个顶点必定会组成一个矩形，而actual_area = expected_area可以保证不会有重叠区域。这两项已经构成了充分条件。

Nov 18 '21 09:11 Park-J-lab

Java版

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE, X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
        Set<String> points = new HashSet<>();
        int actual_area = 0;
        for(int[] item : rectangles){
            int x1 = item[0], y1 = item[1], x2 = item[2], y2 = item[3];
            X1 = Math.min(X1, x1);Y1 = Math.min(Y1, y1);
            X2 = Math.max(X2, x2);Y2 = Math.max(Y2, y2);
            actual_area += (x2-x1)*(y2-y1);
            int[] p1 = new int[]{x1,y1};int[] p2 = new int[]{x1,y2};
            int[] p3 = new int[]{x2,y1};int[] p4 = new int[]{x2,y2};
            for(int[] p : new int[][]{p1,p2,p3,p4}){
                String s = p[0] + "," + p[1];
                if(points.contains(s)){
                    points.remove(s);
                }else{
                    points.add(s);
                }
            }
        }
        int expected_area = (X2-X1)*(Y2-Y1);
        if(actual_area != expected_area){
            return false;
        }
        if(points.size() != 4) return false;
        String s1 = X1 + "," + Y1;
        String s2 = X1 + "," + Y2;
        String s3 = X2 + "," + Y1;
        String s4 = X2 + "," + Y2;
        if(!points.contains(s1)) return false;
        if(!points.contains(s2)) return false;
        if(!points.contains(s3)) return false;
        if(!points.contains(s4)) return false;
        return true;
    }
}