小编joj*_*ark的帖子

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

输入:二维点数组 ((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
Run Code Online (Sandbox Code Playgroud)

每条边长均为 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
Run Code Online (Sandbox Code Playgroud)

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


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

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

algorithm dynamic-programming time-complexity

1
推荐指数
1
解决办法
113
查看次数