我有一组点,我的目标是选择两个点,以便最大化由两个点形成的矩形的面积(一个代表左下角,另一个代表右上角)。
我可以通过只做两个 for 循环并计算每个可能的区域来在 O(n^2) 中做到这一点,但我认为必须有一个更有效的解决方案:
max_area = 0
for p1 in points:
for p2 in points:
area = p2[0]p2[1] + p1[0]p1[1] - p2[1]p1[0] - p2[0]p1[1]
if area > max_area:
max_area = area
很明显,我想用原点 (0,0) 最大化第二个点的面积(所以 p2[0]p2[1]),但我不确定如何继续。
最佳答案
是的,有一个 O(n log n) 时间算法(应该与元素差异性下界匹配)。
找到,对于每个 p1
就足够了, p2
它具有最大的矩形区域,然后返回整体最大的。这可以表示为一个 3D 极值点问题:每个 p2
产生 3D 点 (p2[0], p2[1], p2[0] p2[1])
, 和每个 p1
产生 3D 矢量 (-p1[0], -p1[1], 1)
,我们想要最大化点积(技术上加上 p1[0] p1[1]
,但这个常数偏移量不会影响答案)。然后我们“只是”必须遵循柯克帕特里克 1983 年的构造。
关于algorithm - 从一组点中找到最大矩形的高效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69275956/