求点集中可构成的最大非轴对齐矩形面积的高效解法问询

核心思路 #

矩形的核心几何特征是：两条对角线中点重合且长度相等。基于此，我们可以跳过暴力枚举所有四点组合的低效方式，转而通过哈希表分组点对来快速定位可构成矩形的点集：

• 遍历所有点对，用「中点坐标的2倍（避免浮点）+ 对角线长度平方」作为键，将点对存入哈希表
• 同一键下的任意两个点对，均可构成一个矩形，计算其面积并维护最大值

具体步骤 #

1. 预处理点集：将所有点转为元组，存入哈希集合，便于快速查重。
2. 遍历点对并分组：
   • 遍历所有i<j的点对 p1=(x1,y1)、p2=(x2,y2)
   • 计算键值：中点坐标乘2得到整数对 (x1+x2, y1+y2)，对角线长度平方 (x1-x2)² + (y1-y2)²，将两者组合为哈希表的键
   • 将点对 (p1,p2) 添加到对应键的列表中
3. 计算矩形面积并更新最大值：
   • 遍历哈希表中每个键对应的点对列表，对列表中每两个不同的点对 (p1,p2) 和 (p3,p4)：
     • 确保四个点互不重复（跳过重复点的情况）
     • 计算矩形面积：利用向量叉积的绝对值，公式为 |(p3[0]-p1[0])*(p2[1]-p1[1]) - (p3[1]-p1[1])*(p2[0]-p1[0])|
     • 若该面积大于当前最大值，则更新最大值
4. 输出结果：最终记录的最大值即为所求

复杂度分析 #

• 时间复杂度：O(n²)，其中n为点的数量。遍历所有点对需O(n²)，同一键下点对组合的总运算量不超过O(n²)
• 空间复杂度：O(n²)，最坏情况下所有点对的键值均不同，哈希表需存储全部点对

示例验证 #

示例1 #

输入：[[1,2], [2,1], [1,0], [0,1]]

• 分组时，点对(1,2)-(1,0)和(2,1)-(0,1)的键均为(2,3)（中点乘2）+4（对角线平方）
• 计算面积：向量(2,1)-(1,2)=(1,-1)，向量(0,1)-(1,2)=(-1,-1)，叉积绝对值为|1*(-1) - (-1)*(-1)|=2，与输出一致

示例2 #

输入：[[0,1], [2,1], [1,1], [1,0], [2,0]]

• 唯一符合条件的分组是点对(2,1)-(1,0)和(2,0)-(1,1)，键为(3,1)（中点乘2）+2（对角线平方）
• 计算面积：向量(2,0)-(2,1)=(0,-1)，向量(1,1)-(2,1)=(-1,0)，叉积绝对值为|0*0 - (-1)*(-1)|=1，与输出一致

实现注意事项 #

• 避免浮点误差：用中点坐标的2倍（整数）代替原始中点，对角线用平方值（整数）作为键的一部分，彻底规避浮点精度问题
• 减少重复计算：仅遍历i<j的点对，避免处理(p1,p2)和(p2,p1)这种重复点对
• 点去重：若输入点集中存在重复点，提前过滤，避免无效计算

内容的提问来源于stack exchange，提问作者jojo_mark