Perfect Rectangle

https://leetcode.com/problems/perfect-rectangle/#/solutions

这道题看着挺tricky，方块需要完美的拼出长方形。可以看出当有很多很多小方块时，每个方块大小不一样时，直接判断是否时完美长方形是很难的。一种思维是将条件转化为其他条件，比如面积来判断。开始想的是判断面积相等， 同时判断所有的点都在内部。

• 错误尝试

• 面积相等

• 所有的点都在顶点内部（maxx1，maxy1，maxx2， maxy2）组成的顶点一定在长方形上

• 忽略点：可能存在overlap，导致长方形面积一样，顶点符合要求。[[0,0,1,1],[0,1,3,2],[1,0,2,2]]

public class Solution {

    public boolean isRectangleCover(int[][] rectangles) {
        int area=0;
        int x1 = Integer.MAX_VALUE; int x2 = Integer.MIN_VALUE;
        int y1 = Integer.MAX_VALUE; int y2 = Integer.MIN_VALUE;
        for(int[] r : rectangles){
            x1 = Math.min(x1, r[0]);
            y1 = Math.min(y1, r[1]);
            x2 = Math.max(x2, r[2]);
            y2 = Math.max(y2, r[3]);
            area+=(r[2]-r[0])*(r[3]-r[1]);
        }
        System.out.println(area);
        System.out.println((x2-x1)*(y2-y1));
        if(area!=(x2-x1)*(y2-y1)) return false;
        int count = 0;
        for(int[] r:rectangles){
            if(r[0]==x1&&r[1]==y1) count++;
            else if(r[2]==x2&&r[3]==y2) count++;
        }
        System.out.println(x1+" "+y1+" "+x2+" "+y2);
        System.out.println(count);
        return count==2||count>=rectangles.length;
    }
}

• 面积相等

• 除顶点外所有方块的点出现了偶数次，完美拼接

public class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        // two conditions
        // 1.the area of large rectangle and the sum area of small rectangles
        // 2.every points should appear even times except 4 corners
        HashSet<String> set = new HashSet<String>();
        int area = 0;
        int x1 = Integer.MAX_VALUE, x2 = Integer.MIN_VALUE, y1 = Integer.MAX_VALUE, y2 = Integer.MIN_VALUE;
        for(int i=0;i<rectangles.length;i++){
            x1 = Math.min(x1, rectangles[i][0]);
            y1 = Math.min(y1, rectangles[i][1]);
            x2 = Math.max(x2, rectangles[i][2]);
            y2 = Math.max(y2, rectangles[i][3]);

            area += (rectangles[i][2]-rectangles[i][0]) * (rectangles[i][3]-rectangles[i][1]);

            String s1 = rectangles[i][0] + " " + rectangles[i][1];
            String s2 = rectangles[i][0] + " " + rectangles[i][3];
            String s3 = rectangles[i][2] + " " + rectangles[i][1];
            String s4 = rectangles[i][2] + " " + rectangles[i][3];
            if(!set.add(s1)) set.remove(s1);
            if(!set.add(s2)) set.remove(s2);
            if(!set.add(s3)) set.remove(s3);
            if(!set.add(s4)) set.remove(s4);
        }
         if (!set.contains(x1 + " " + y1) || !set.contains(x1 + " " + y2) || !set.contains(x2 + " " + y1) || !set.contains(x2 + " " + y2) || set.size() != 4) return false;

        return area == (x2-x1) * (y2-y1);
    }
}

Convex Polygon

高中数学，掌握算内积的方式，(BAx * BCy - BAy * BCx)。内积全正全负return false

public class Solution {
    public boolean isConvex(List<List<Integer>> points) {
        // For each set of three adjacent points A, B, C, find the cross product AB · BC. If the sign of
        // all the cross products is the same, the angles are all positive or negative (depending on the
        // order in which we visit them) so the polygon is convex.
        boolean gotNegative = false;
        boolean gotPositive = false;
        int numPoints = points.size();
        int B, C;
        for (int A = 0; A < numPoints; A++) {
            // Trick to calc the last 3 points: n - 1, 0 and 1.
            B = (A + 1) % numPoints;
            C = (B + 1) % numPoints;

            int crossProduct =
                crossProductLength(
                    points.get(A).get(0), points.get(A).get(1),
                    points.get(B).get(0), points.get(B).get(1),
                    points.get(C).get(0), points.get(C).get(1));
            if (crossProduct < 0) {
                gotNegative = true;
            }
            else if (crossProduct > 0) {
                gotPositive = true;
            }
            if (gotNegative && gotPositive) return false;
        }

        // If we got this far, the polygon is convex.
        return true;
    }

    // Return the cross product AB x BC.
    // The cross product is a vector perpendicular to AB and BC having length |AB| * |BC| * Sin(theta) and
    // with direction given by the right-hand rule. For two vectors in the X-Y plane, the result is a
    // vector with X and Y components 0 so the Z component gives the vector's length and direction.
    private int crossProductLength(int Ax, int Ay, int Bx, int By, int Cx, int Cy)
    {
        // Get the vectors' coordinates.
        int BAx = Ax - Bx;
        int BAy = Ay - By;
        int BCx = Cx - Bx;
        int BCy = Cy - By;

        // Calculate the Z coordinate of the cross product.
        return (BAx * BCy - BAy * BCx);
    }
}

Construct the Rectangle

public class Solution {
    public int[] constructRectangle(int area) {
        int x = (int)Math.sqrt((double)area);

        for(int i=x;i>=0;i--){
            if(area%i==0){
                return new int[]{area/i, i};
            }
        }
        return new int[2];
    }
}

Two Rectangles Overlap

Rectangle Area

这两个题放到一起，一个道理。在判断两个长方形有重合，那么两个长方形左边界的最大值一定小于右边界的最小值。两个长方形上边界的最小值一定大于下边界的最大值。

重合面积是(右边界min－左边界max)*(上边界min－下边界max)。不需要考虑两个长方形的相对位置，判断大小即可。

public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int x1 = Math.max(A,E);
        int y1 = Math.max(B,F);

        int x2 = Math.min(C,G);
        int y2 = Math.min(D,H);

        int ol = 0;
        if(x2<=x1 || y2<=y1) ol = 0;
        else ol = (x2-x1)*(y2-y1);

        return (C-A)*(D-B) + (G-E)*(H-F) - ol;
    }
}