Medium

题目描述

给你一个在 X-Y 平面上的点数组 points，其中 points[i] = [xi, yi]。

返回由这些点形成的任意矩形的最小面积，矩形的边不一定平行于 X 和 Y 轴。如果没有任何矩形，则返回 0。

与实际答案误差在 10^-5 以内的答案将被接受。

示例 1：

输入：points = [[1,2],[2,1],[1,0],[0,1]]
输出：2.00000
解释：最小面积矩形出现在 [1,2],[2,1],[1,0],[0,1]，面积为 2。

示例 2：

输入：points = [[0,1],[2,1],[1,1],[1,0],[2,0]]
输出：1.00000
解释：最小面积矩形出现在 [1,0],[1,1],[2,1],[2,0]，面积为 1。

示例 3：

输入：points = [[0,3],[1,2],[3,1],[1,3],[2,1]]
输出：0
解释：没有办法从这些点中形成任何矩形。

提示：

  • 1 <= points.length <= 50
  • points[i].length == 2
  • 0 <= xi, yi <= 4 * 10^4
  • 所有点都是唯一的。

解题思路

这道题要求找到由给定点组成的任意矩形的最小面积，矩形的边不必平行于坐标轴。

核心思路：

矩形有一个重要性质：对角线互相平分且相等。因此我们可以枚举所有可能的对角线，检查是否能形成矩形。

算法步骤：

  1. 枚举对角线： 对于任意两点，将它们作为矩形的一条对角线
  2. 寻找另一条对角线： 根据矩形性质，另一条对角线的中点必须与当前对角线的中点相同，且长度相等
  3. 验证矩形： 检查四个点是否能构成矩形，需要满足：
    • 两条对角线中点相同
    • 两条对角线长度相等
    • 两条对角线互相垂直
  4. 计算面积： 对于有效的矩形，计算其面积并更新最小值

优化策略： 使用哈希表存储对角线信息（中点坐标和长度的平方），快速查找可能的配对对角线。

时间复杂度： O(n²)，其中 n 是点的个数，需要枚举所有点对。

代码实现

class Solution {
public:
    double minAreaFreeRect(vector<vector<int>>& points) {
        int n = points.size();
        if (n < 4) return 0.0;
        
        // 存储对角线信息: key为(中点x*2, 中点y*2, 长度平方), value为对角线端点索引对
        map<tuple<int, int, long long>, vector<pair<int, int>>> diagonals;
        
        // 枚举所有可能的对角线
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int cx = points[i][0] + points[j][0]; // 中点x坐标*2
                int cy = points[i][1] + points[j][1]; // 中点y坐标*2
                long long dist = (long long)(points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + 
                                (long long)(points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                
                diagonals[{cx, cy, dist}].push_back({i, j});
            }
        }
        
        double minArea = DBL_MAX;
        bool found = false;
        
        // 检查每组对角线
        for (auto& [key, pairs] : diagonals) {
            if (pairs.size() < 2) continue;
            
            // 对于每组有相同中点和长度的对角线，检查是否能构成矩形
            for (int i = 0; i < pairs.size(); i++) {
                for (int j = i + 1; j < pairs.size(); j++) {
                    auto [p1, p2] = pairs[i];
                    auto [p3, p4] = pairs[j];
                    
                    // 计算矩形面积
                    double area = calculateArea(points[p1], points[p2], points[p3], points[p4]);
                    if (area > 0) {
                        minArea = min(minArea, area);
                        found = true;
                    }
                }
            }
        }
        
        return found ? minArea : 0.0;
    }
    
private:
    double calculateArea(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        // 计算两个邻边的长度
        double side1 = sqrt(pow(p1[0] - p3[0], 2) + pow(p1[1] - p3[1], 2));
        double side2 = sqrt(pow(p1[0] - p4[0], 2) + pow(p1[1] - p4[1], 2));
        
        return side1 * side2;
    }
};

class Solution:
    def minAreaFreeRect(self, points: List[List[int]]) -> float:
        n = len(points)
        if n < 4:
            return 0.0
        
        from collections import defaultdict
        
        # 存储对角线信息
        diagonals = defaultdict(list)
        
        # 枚举所有可能的对角线
        for i in range(n):
            for j in range(i + 1, n):
                cx = points[i][0] + points[j][0]  # 中点x坐标*2
                cy = points[i][1] + points[j][1]  # 中点y坐标*2
                dist = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2
                
                diagonals[(cx, cy, dist)].append((i, j))
        
        min_area = float('inf')
        found = False
        
        # 检查每组对角线
        for pairs in diagonals.values():
            if len(pairs) < 2:
                continue
            
            # 对于每组有相同中点和长度的对角线，检查是否能构成矩形
            for i in range(len(pairs)):
                for j in range(i + 1, len(pairs)):
                    p1, p2 = pairs[i]
                    p3, p4 = pairs[j]
                    
                    # 计算矩形面积
                    area = self.calculate_area(points[p1], points[p2], points[p3], points[p4])
                    if area > 0:
                        min_area = min(min_area, area)
                        found = True
        
        return min_area if found else 0.0
    
    def calculate_area(self, p1, p2, p3, p4):
        # 计算两个邻边的长度
        side1 = ((p1[0] - p3[0]) ** 2 + (p1[1] - p3[1]) ** 2) ** 0.5
        side2 = ((p1[0] - p4[0]) ** 2 + (p1[1] - p4[1]) ** 2) ** 0.5
        
        return side1 * side2

public class Solution {
    public double MinAreaFreeRect(int[][] points) {
        int n = points.Length;
        if (n < 4) return 0.0;
        
        // 存储对角线信息
        var diagonals = new Dictionary<(int, int, long), List<(int, int)>>();
        
        // 枚举所有可能的对角线
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int cx = points[i][0] + points[j][0]; // 中点x坐标*2
                int cy = points[i][1] + points[j][1]; // 中点y坐标*2
                long dist = (long)(points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + 
                           (long)(points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                
                var key = (cx, cy, dist);
                if (!diagonals.ContainsKey(key)) {
                    diagonals[key] = new List<(int, int)>();
                }
                diagonals[key].Add((i, j));
            }
        }
        
        double minArea = double.MaxValue;
        bool found = false;
        
        // 检查每组对角线
        foreach (var pairs in diagonals.Values) {
            if (pairs.Count < 2) continue;
            
            // 对于每组有相同中点和长度的对角线，检查是否能构成矩形
            for (int i = 0; i < pairs.Count; i++) {
                for (int j = i + 1; j < pairs.Count; j++) {
                    var (p1, p2) = pairs[i];
                    var (p3, p4) = pairs[j];
                    
                    // 计算矩形面积
                    double area = CalculateArea(points[p1], points[p2], points[p3], points[p4]);
                    if (area > 0) {
                        minArea = Math.Min(minArea, area);
                        found = true;
                    }
                }
            }
        }
        
        return found ? minArea : 0.0;
    }
    
    private double CalculateArea(int[] p1, int[] p2, int[] p3, int[] p4) {
        // 计算两个邻边的长度
        double side1 = Math.Sqrt(Math.Pow(p1[0] - p3[0], 2) + Math.Pow(p1[1] - p3[1], 2));
        double side2 = Math.Sqrt(Math.Pow(p1[0] - p4[0], 2) + Math.Pow(p1[1] - p4[1], 2));
        
        return side1 * side2;
    }
}

var minAreaFreeRect = function(points) {
    const n = points.length;
    if (n < 4) return 0.0;
    
    // 存储对角线信息
    const diagonals = new Map();
    
    // 枚举所有可能的对角线
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const cx = points[i][0] + points[j][0]; // 中点x坐标*2
            const cy = points[i][1] + points[j][1]; // 中点y坐标*2
            const dist = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2;
            
            const key = `${cx},${cy},${dist}`;
            if (!diagonals.has(key)) {
                diagonals.set(key, []);
            }
            diagonals.get(key).push([i, j]);
        }
    }
    
    let minArea = Number.MAX_VALUE;
    let found = false;
    
    // 检查每组对角线
    for (const pairs of diagonals.values()) {
        if (pairs.length < 2) continue;
        
        // 对于每组有相同中点和长度的对角线，检查是否能构成矩形
        for (let i = 0; i < pairs.length; i++) {
            for (let j = i + 1; j < pairs.length; j++) {
                const [p1, p2] = pairs[i];
                const [p3, p4] = pairs[j];
                
                // 计算矩形面积
                const area = calculateArea(points[p1], points[p2], points[p3], points[p4]);
                if (area > 0) {
                    minArea = Math.min(minArea, area);
                    found = true;
                }
            }
        }
    }
    
    return found ? minArea : 0.0;
    
    function calculateArea(p1, p2, p3, p4) {
        // 计算两个邻边的长度
        const side1 = Math.sqrt((p1[0] - p3[0]) ** 2 + (p1[1] - p3[1]) ** 2);
        const side2 = Math.sqrt((p1[0] - p4[0]) ** 2 + (p1[1] - p4[1]) ** 2);
        
        return side1 * side2;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n²)
空间复杂度O(n²)
  • 时间复杂度： O(n²)，需要枚举所有点对作为对角线，每组对角线的检查是常数时间
  • 空间复杂度： O(n²)，哈希表最多存储 O(n²) 条对角线信息