输入:二维点数组 ((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 个点的所有可能组合,看看它们是否形成一个矩形,然后比较它们的面积,但对于大输入来说太慢了......