963. Minimum Area Rectangle II

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. 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.

Rust Solution

struct Solution;
use std::collections::HashMap;

type Cross = (i32, i32, i32);
type Point = (i32, i32);

impl Solution {
    fn min_area_free_rect(points: Vec<Vec<i32>>) -> f64 {
        let mut hm: HashMap<Cross, Vec<Point>> = HashMap::new();
        let n = points.len();
        let mut res = std::f64::MAX;
        for i in 0..n {
            for j in i + 1..n {
                let x1 = points[i][0];
                let x2 = points[j][0];
                let y1 = points[i][1];
                let y2 = points[j][1];
                let c = (
                    x1 + x2,
                    y1 + y2,
                    (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1),
                );
                let points = hm.entry(c).or_default();
                for point in points.iter() {
                    let e1 = Self::edge(x1, y1, point.0, point.1);
                    let e2 = Self::edge(x2, y2, point.0, point.1);
                    res = res.min(e1 * e2);
                }
                points.push((x1, y1));
            }
        }
        if res == std::f64::MAX {
            0.0
        } else {
            res
        }
    }
    fn edge(x1: i32, y1: i32, x2: i32, y2: i32) -> f64 {
        (((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)) as f64).sqrt()
    }
}

#[test]
fn test() {
    use assert_approx_eq::assert_approx_eq;
    let points = vec_vec_i32![[1, 2], [2, 1], [1, 0], [0, 1]];
    let res = 2.0;
    assert_approx_eq!(Solution::min_area_free_rect(points), res);
    let points = vec_vec_i32![[0, 1], [2, 1], [1, 1], [1, 0], [2, 0]];
    let res = 1.0;
    assert_approx_eq!(Solution::min_area_free_rect(points), res);
    let points = vec_vec_i32![[0, 3], [1, 2], [3, 1], [1, 3], [2, 1]];
    let res = 0.0;
    assert_approx_eq!(Solution::min_area_free_rect(points), res);
    let points = vec_vec_i32![
        [3, 1],
        [1, 1],
        [0, 1],
        [2, 1],
        [3, 3],
        [3, 2],
        [0, 2],
        [2, 3]
    ];
    let res = 2.0;
    assert_approx_eq!(Solution::min_area_free_rect(points), res);
}

Having problems with this solution? Click here to submit an issue on github.