LeetCode: Minimum Area Rectangle II

Posted on August 5, 2019July 26, 2020 by braindenny

Minimum Area Rectangle II

Similar Problems:

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:

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:

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:

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:

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 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.
Answers within 10^-5 of the actual value will be accepted as correct.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/minimum-area-rectangle-ii
// Basic Ideas: array + hashmap
//   From 3 points, we can get the fourth point to make a rectangle
// Complexity: Time O(n^3), Space O(1)
import "math"
func getDis(points [][]int, i int, j int) int {
    v1 := points[i][0]-points[j][0]
    v2 := points[i][1]-points[j][1]
    return v1*v1+v2*v2
}

func getArea(points [][]int, m map[[2]int]bool, i int, j int, k int) float64 {
    a := getDis(points, i, j)
    b := getDis(points, j, k)
    c := getDis(points, i, k)
    // c would be the longest length
    if c < a {
        return getArea(points, m, i, k, j) 
    }
    if c < b {
        return getArea(points, m, j, i, k)
    }
    // Not a valid rectangle
    if a+b != c {
        return float64(1<<31-1)
    }
    x := points[i][0]+points[k][0]-points[j][0]
    y := points[i][1]+points[k][1]-points[j][1]
    if _, ok := m[[2]int{x, y}]; !ok {
        return float64(1<<31-1)
    } else {
        return math.Sqrt(float64(a))*math.Sqrt(float64(b))
    }
}

func minAreaFreeRect(points [][]int) float64 {
    res := float64(1<<31-1)
    m := map[[2]int]bool{}
    for _, p := range points {
        m[[2]int{p[0], p[1]}] = true
    }
    for i:=0; i+3<len(points); i++ {
        for j:=i+1; j+2<len(points); j++ {
            for k:=j+1; k+1<len(points); k++ {
                v := getArea(points, m, i, j, k)
                if v < res {
                    res = v
                }
            }
        }
    }
    if res == float64(1<<31-1) {
        res = 0
    }
    return res
}

Post Views: 0