gpt4 book ai didi

arrays - 找到三角形最大可能面积的最快方法

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:01:53 24 4
gpt4 key购买 nike

假设我们在平面上有一组点,每个点都由一对整数坐标描述。有没有一种方法可以比 O(n^3) 算法更快地找到顶点在此点上且面积最大的三角形?

最佳答案

  1. 找到凸包。
  2. 对于位于凸包上的每点 (A, B),找到第三个点 C,它给出了三角形 ABC 的最大面积。这可以在 O(log n) 中使用二进制搜索来完成。

要进行二分搜索,请按某种顺序(例如逆时针)在凸包上排列点。 A 和 B 之间有两个点序列,一个是从 A 到 B,另一个是从 B 到 A。分别考虑每一个。

二分查找步骤如下。在点的区间中间取三个连续的点C、C'、C''。计算三个区域 CAB、C'AB、C''AB。如果C'是三者中最大的,则为全局最大值,搜索结束。如果 C 最大,则最大值位于区间的左半部分。如果 C'' 最大,则最大值在右半部分。 (编辑:注意,新间隔的一端应包含 C')。

那里有一个 O(n^2 log n) 的算法。

编辑 2:this question 的答案展示了如何更快地做到这一点。您可以结合这两种方法来做得更好(在构建凸包后的 O(log n) 中,尽管构建凸包仍然是 O(n log n))。

关于arrays - 找到三角形最大可能面积的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19876594/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com