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;
            
        }
    }
    
  • // OJ: https://leetcode.com/problems/minimum-area-rectangle-ii/
    // Time: O(N^3)
    // Space: O(N)
    // Ref: https://leetcode.com/problems/minimum-area-rectangle-ii/solution/
    class Solution {
        double dist(vector<int> &a, vector<int> &b) {
            return sqrt(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2));
        }
    public:
        double minAreaFreeRect(vector<vector<int>>& A) {
            int N = A.size();
            set<vector<int>> s(begin(A), end(A));
            double ans = DBL_MAX;
            for (int i = 0; i < N; ++i) {
                auto &p1 = A[i];
                for (int j = 0; j < N; ++j) {
                    if (i == j) continue;
                    auto &p2 = A[j];
                    for (int k = j + 1; k < N; ++k) {
                        if (k == i) continue;
                        auto &p3 = A[k], p4 = vector<int>{ p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1] };
                        if (s.count(p4)) {
                            int dot = (p2[0] - p1[0]) * (p3[0] - p1[0]) + (p2[1] - p1[1]) * (p3[1] - p1[1]);
                            if (dot == 0) {
                                double area = dist(p1, p2) * dist(p1, p3);
                                ans = min(ans, area);
                            }
                        }
                    }
                }
            }
            return ans == DBL_MAX ? 0 : ans;
        }
    };
    
  • class Solution(object):
        def minAreaFreeRect(self, points):
            """
            :type points: List[List[int]]
            :rtype: float
            """
            N = len(points)
            # (l^2, x#, y#) : [(0,1), (1,2)]
            d = collections.defaultdict(list)
            for i in range(N - 1):
                pi = points[i]
                for j in range(i + 1, N):
                    pj = points[j]
                    l = (pi[0] - pj[0]) ** 2 + (pi[1] - pj[1]) ** 2
                    x = (pi[0] + pj[0]) / 2.0
                    y = (pi[1] + pj[1]) / 2.0
                    d[(l, x, y)].append((i, j))
            res = float("inf")
            for l in d.values():
                M = len(l)
                for i in range(M - 1):
                    p0, p2 = points[l[i][0]], points[l[i][1]]
                    for j in range(i + 1, M):
                        p1, p3 = points[l[j][0]], points[l[j][1]]
                        d1 = math.sqrt((p0[0] - p1[0]) ** 2 + (p0[1] - p1[1]) ** 2)
                        d2 = math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
                        area = d1 * d2
                        res = min(res, area)
            return 0 if res == float('inf') else res
    

All Problems

All Solutions