Formatted question description: https://leetcode.ca/all/963.html

963. Minimum Area Rectangle II

Level

Medium

Description

Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Image text

Input: [[1,2],[2,1],[1,0],[0,1]]

Output: 2.00000

Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2:

Image text

Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]

Output: 1.00000

Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3:

Image text

Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]

Output: 0

Explanation: There is no possible rectangle to form from these points.

Example 4:

Image text

Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]

Output: 2.00000

Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.

Note:

  1. 1 <= points.length <= 50
  2. 0 <= points[i][0] <= 40000
  3. 0 <= points[i][1] <= 40000
  4. All points are distinct.
  5. Answers within 10^-5 of the actual value will be accepted as correct.

Solution

For each group of three points, if the three points form a right triangle, then find the right angle and try to find another point such that the four points can form a rectangle, and calculate the area. If a rectangle is found, update the minimum area. If no rectangle is found, return 0.

class Solution {
    public double minAreaFreeRect(int[][] points) {
        if (points == null || points.length < 4 || points[0].length != 2)
            return 0;
        int length = points.length;
        double minArea = Double.MAX_VALUE;
        int end1 = length - 3, end2 = length - 2, end3 = length - 1;
        for (int i = 0; i < end1; i++) {
            int[] point1 = points[i];
            for (int j = i + 1; j < end2; j++) {
                int[] point2 = points[j];
                for (int k = j + 1; k < end3; k++) {
                    int[] point3 = points[k];
                    if (isRightAngle(point1, point2, point3)) {
                        for (int m = k + 1; m < length; m++) {
                            int[] point4 = points[m];
                            double area = rectangleArea(point1, point2, point3, point4);
                            if (area > 0)
                                minArea = Math.min(minArea, area);
                        }
                    } else if (isRightAngle(point2, point3, point1)) {
                        for (int m = k + 1; m < length; m++) {
                            int[] point4 = points[m];
                            double area = rectangleArea(point2, point3, point1, point4);
                            if (area > 0)
                                minArea = Math.min(minArea, area);
                        }
                    } else if (isRightAngle(point3, point1, point2)) {
                        for (int m = k + 1; m < length; m++) {
                            int[] point4 = points[m];
                            double area = rectangleArea(point3, point1, point2, point4);
                            if (area > 0)
                                minArea = Math.min(minArea, area);
                        }
                    }
                }
            }
        }
        return minArea == Double.MAX_VALUE ? 0 : minArea;
    }

    public double rectangleArea(int[] point1, int[] point2, int[] point3, int[] point4) {
        int x = point1[0] + point3[0] - point2[0], y = point1[1] + point3[1] - point2[1];
        if (point4[0] == x && point4[1] == y) {
            double side1 = Math.sqrt((point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1]));
            double side2 = Math.sqrt((point2[0] - point3[0]) * (point2[0] - point3[0]) + (point2[1] - point3[1]) * (point2[1] - point3[1]));
            return side1 * side2;
        } else
            return 0;
    }

    public boolean isRightAngle(int[] point1, int[] point2, int[] point3) {
        return (point1[0] - point2[0]) * (point2[0] - point3[0]) + (point1[1] - point2[1]) * (point2[1] - point3[1]) == 0;
        
    }
}

All Problems

All Solutions