math - 内部有 N 个点的三角形的数量

Question

给定平面上的一些点（最多 500 个点），没有 3 个共线。我们必须确定其顶点来自给定点并且其中包含恰好 N 个点的三角形的数量。如何有效地解决这个问题？天真的 O(n^4) 算法太慢了。有更好的方法吗？

Answer 1

您可以尝试将三角形视为三个半空间的交集。要找到三角形 A、B、C 内的点数，首先考虑沿 AB 方向的无限线一侧的点集。让这些集合 L(AB) 和 R(AB) 用于左右的点。类似地，您对其他两条边也一样，并构建集合 L(AC) 和 R(AC) 以及集合 L(BC) 和 R(BC)。

所以 ABC 中的点数将是 L(AB)、L(AC) 和 L(BC) 交点的点数。（根据三角形的方向，您可能需要考虑 R(AB)）。

现在如果我们要考虑全套 500 点。首先取所有点 AB 对并构造集合 L(AB) 和 R(AB)。这将需要 O(n^3) 次操作。

接下来我们测试所有三角形并找到三组的交点。如果我们对集合使用一些哈希表结构，那么找到交点就像一个哈希表查找。如果 L(AB) 有 l 个元素，L(AC) 有 m 个元素，L(BC) 有 n 个元素。说 l > m > n。对于 L(BC) 中的每个点，我们需要在 L(AC) 和 L(BC) 中进行查找，这样最多可以查找 2n 个哈希表。

考虑几何查找表可能会更快。将您的整个域划分为一个粗略的网格，例如 10 x 10 网格。然后我们可以将每个点放入一个集合 G(i,j)。然后我们可以将集合 L(AB) 拆分为每个网格单元。假设将这些集合称为 L(AB,i,j) 和 R(AB,i,j)。在测试交叉点时，首先要确定哪些网格单元位于交叉点中。这极大地减少了搜索空间，并且由于每个集合 L(AB,i,j) 包含的成员较少，因此哈希表查找也会减少。

Answer 2

实际上我最近碰巧遇到了类似的问题，但唯一的区别是大约有 300 分，我使用 bitset (C++ STL) 解决了它。对于每一对点，比如 (x[i],y[i]) 和 (x[j],y[j])，我形成了一个 bitset<302>B[i][j] 和 B[i] [j][k] 如果第 k 个点在从点 i 到点 j 的线段上方，则存储 1，否则我将存储 0。

现在以蛮力的方式，我得到三个点以形成一个三角形，比如说 (x[i],y[i]), (x[j],y[j]) 和 (x[k],y [k])，然后一个点，比如第 z 个点，如果 B[i][j][z]==B[i][j][k] && B[j][k] 将在三角形内[z]==B[j][k][i] && B[k][i][z]==B[k][i][j] 因为三角形内的点会在边上显示相似的符号三角形作为三角形的第三个点（不在这一边的一个）。所以我得到三个位集变量 P=B[i][j], Q=B[j][k] 和 R=B[k][i] 并在那里按位并应用 count() 函数给我有效位数，因此三角形内的点数。但是请确保您更改变量 P 使得它给出 B[i][j][k]=1 如果不是，那么按位而不是（~）这个变量。

尽管上述解决方案是针对特定问题的，但我希望它有所帮助。这是问题链接：http ://usaco.org/current/index.php?page=viewproblem&cpid=660