从点列表中查找可能的矩形最大面积（不一定与轴平行）的函数

Question

输入：二维点数组 ((x, y), (x2, y2), ...)
输出：最大可能矩形的区域，其 4 个角为给定点中的 4 个点。

注意：矩形不必平行于任何轴，至少可以用一组点制作一个矩形

---

示例 1：
输入：[[1,2], [2,1], [1,0], [0,1]]
输出：2
解释：
矩形在 2d 平面上如下所示：

2   x
1 x   x
0   x
  0 1 2

每条边长均为 sqrt(2)，因此面积为 2。

示例 2：
输入：[[0,1], [2,1], [1,1], [1,0], [2,0]]
输出：1

说明：
飞机：

2
1 x x x
0   x x
  0 1 2

唯一可能的矩形是边长为 1 的正方形，因此面积为 1。

---

我将不胜感激任何解决这个问题的帮助，老实说我不知道​​如何提高效率。有可能吗？

我尝试了暴力破解，即检查 4 个点的所有可能组合，看看它们是否形成一个矩形，然后比较它们的面积，但对于大输入来说太慢了......

Answer 1

O(n^2) 算法：

1. 生成角度 <= 45 度且 > -45 度的所有点(p1,p2)对。p1.x < p2.x每个矩形在此列表中都有一个“顶”和“底”边。
2. 按角度和距离将这些对分开。每个矩形的顶部和底部都位于同一分区中。
3. 对于每个（角度，距离），将这些对划分为p1.x*(p2.x-p1.x) + p1.y*(p2.y-p1.y)。每个矩形的顶边和底边都在同一个分区中，每个分区中的每对对都会形成一个矩形。
4. 对于每个结果分区，找到具有 min 和 max 的点p1.y。这些构成了分区中最大的矩形。