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

EN

你可以试着把三角形想象成三个半空间的交集。要计算三角形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 * 10的网格。然后我们可以把每个点放到一个集合G(i，j)中。然后，我们可以将集合L(AB)分割为每个网格单元。比方说称这些集合为L(AB，i，j)和R(AB，i，j)。在测试交叉点时，首先计算出哪些网格单元位于交叉点。这极大地减少了搜索空间，并且由于每个集合L(AB，i，j)包含的成员更少，因此将有更少的哈希表查找。

实际上，我最近碰巧遇到了类似的问题，但唯一的区别是大约有300个点，我使用位集(C++ STL)解决了它。对于每一对点，例如(xi，yi)和(xj，yj)，我形成了一个bitset<302>Bi，如果第k个点在从点i到点j的线段之上，则存储1，否则我将存储0。

现在我以一种蛮力的方式得到三个点，从而形成一个三角形，比如说(xi，yi)，(xj，yj)和(xk，yk)，然后一个点，比如说z点，如果Biz==Bik && Bjz==Bji && Bkz==Bkj，会在三角形内，因为三角形内的一个点会显示类似的符号w.r.t。三角形的一条边，作为三角形的第三个点(不在这条边上的点)。所以我得到了三个位集变量P=Bi，Q=Bj和R=Bk，然后按位计算，然后应用count()函数给出有效位数，从而得到三角形内的点数。但一定要更改变量P，这样它就会给出Bik=1，如果不是这样，那么就按位获取这个变量的非(~)。

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