题目重点：矩形不必平行坐标轴，用整数几何避免浮点相等。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 整数坐标，重复坐标归一化；选四个不同点组成非退化矩形，返回最大面积，不存在为0。
- 本文讨论任意方向矩形；只允许轴对齐的版本在追问中单独说明。
解题路线
- 矩形的两对角线有同一中点且长度相等；反过来两个不同点对有此属性，构成等对角线平行四边形，即矩形。
- 对每点对(a,c)计算key=(ax+cx,ay+cy,平方距离)，不除2、不求平方根。每个key内枚举两条不同对角线，选四端点。
- 面积用相邻边向量叉积绝对值，例如从a到另一对角线两端b/d。不要把两对角线叉积直接当面积，它等于面积两倍。
手动走一遍
点(0,1),(1,0),(2,1),(1,2)组成旋转正方形，两对角线和坐标均(2,2)、平方长4，面积2。轴对齐(0,0),(3,0),(3,2),(0,2)也被覆盖，面积6；只有三点则0。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict
from itertools import combinations
def largest_rectangle(points):
points = list(dict.fromkeys(map(tuple,points)))
groups = defaultdict(list)
for a,c in combinations(points,2):
key = (a[0]+c[0],a[1]+c[1],(a[0]-c[0])**2+(a[1]-c[1])**2)
groups[key].append((a,c))
answer = 0
for diagonals in groups.values():
for (a,c),(b,d) in combinations(diagonals,2):
if len({a,b,c,d}) != 4:
continue
area = abs((b[0]-a[0])*(d[1]-a[1])-(b[1]-a[1])*(d[0]-a[0]))
answer = max(answer,area)
return answer
复杂度
n唯一点，建组O(n²)期望时间/空间；组内枚举Σk²，保守O(n⁴)，可利用同key每点仅一个对点推出k≤n/2，整体O(n³)上界。实际取决于圆上点的分布。
易错点与追问
容易失分的边界
- 矩形对角线中点同但长度不同只是平行四边形。
- 浮点坐标要另定近似几何与误差标准，不能直接用epsilon做哈希等价类。
继续深挖
- 只允许轴对齐时，怎样按横坐标与共同纵坐标对减少工作？
- 返回顶点顺序怎样保证没有自交，且并列最大如何规定？
