要求找出一个面积最大的矩形,满足以下条件:
• 矩形的四个顶点必须均在给定点集中;
• 矩形的边与坐标轴保持平行(即边与x轴和y轴方向一致);
• 矩形的内部以及边界上不包含除这四个顶点以外的任何其他点...给定的所有点都是 唯一 的。
输入: points = [[1,1],[1,3],[3,1],[3,3]]。
输出:4。...初始化:
• 首先,获取输入的点集 points 的长度 n,并初始化最大面积 ans 为 -1,表示初始时没有找到满足条件的矩形。
2. ...• 对于每一对点 (i, j),计算它们的最小和最大 x 和 y 值,得到矩形的边界 (xa, ya, xb, yb):
• xa 是 points[i][0] 和 points[j][0] 的最小值。...总结:
• 算法通过暴力枚举所有可能的点对作为矩形的对角点,然后验证是否能构成满足条件的矩形。
• 由于 n 很小(最多 10),O(n^3) 的复杂度是完全可行的。