给定平面上的点数组，返回任意矩形的最小面积，矩形边不一定平行于坐标轴。
示例 1:
输入：points = [[1,2],[2,1],[1,0],[0,1]]
输出：2.0
提示:
- 1 <= points.length <= 500
- points[i].length == 2
- -10^4 <= points[i][0], points[i][1] <= 10^4
- 所有点互不相同
解析
枚举对角线，根据中点和距离计算矩形的四个顶点，检查是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| var minAreaFreeRect = function (points) {
const map = new Map();
let minArea = Infinity;
for (let i = 0; i < points.length; i++) {
for (let j = i + 1; j < points.length; j++) {
const cx = (points[i][0] + points[j][0]) / 2;
const cy = (points[i][1] + points[j][1]) / 2;
const dist = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2;
const key = `${cx},${cy},${dist}`;
if (map.has(key)) {
const [p1, p2] = map.get(key);
const area = Math.sqrt(dist) * Math.sqrt(
(points[i][0] - p1[0]) ** 2 + (points[i][1] - p1[1]) ** 2
);
minArea = Math.min(minArea, area);
map.get(key).push(points[i]);
} else {
map.set(key, [points[i], points[j]]);
}
}
}
return minArea === Infinity ? 0 : minArea;
};
|
时间复杂度 O(N^2)，空间复杂度 O(N^2)。