最小面积矩形

给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。
如果没有任何矩形，就返回 0。

  • 输入：[[1,1],[1,3],[3,1],[3,3],[2,2]]

  • 输出：4

  • 输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]

  • 输出：2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var minAreaRect = function(points) {
    // 1. map;
    // 2. 左下、右上枚举
    points.sort((a,b) => a[0] - b[0]);
    let m = new Map();
    let res = Infinity;
    for (let [x,y] of points) {
        if (!m.has(x)) m.set(x, new Set());
        m.get(x).add(y);
    }
    for (let i=0; i<points.length-1; i++) {
        for (let j=i+1; j<points.length; j++) {
            let [x1,y1] = points[i];
            let [x2,y2] = points[j];
            if (x1 < x2 && y1 < y2) {
                // [x1, y2], [x2, y1]
                if (m.get(x1).has(y2) && m.get(x2).has(y1)) {
                    res = Math.min(res, (x2-x1)*(y2-y1));
                }
            }
        }
    }
    return res === Infinity ? 0 : res;
};