查找包含在具有给定区域的矩形中的最大点数

Question

给定一个点数组b [0..n-1]，每个点都具有.x和.y坐标。 n可能很大。

为问题设计一个有效的算法：给定一个区域，找出包含在具有给定区域的矩形中的最大点数。

我希望在时间复杂度O（n^2 * k）上完成，其中k是矩形或更好的最大点。

Answer 1

如果您有三角形的顶点，这非常简单。您可以为数组b中的每个点求解交叉积。您可以计算出Cross1 = [AO, AB], Cross2 = [BO, BC], Cross3 = [CO, CA]。

例如Cross1 = AO.x * AB.y - AO.y * AB.x。

每个变量Cross1, Cross2, Cross3必须是相同的符号。

您为每个点检查此点并将点数计入矩形。那么你有kN = O(N)。