查找由点集形成的三角形是否包含原点并给出总数的算法？

Question

输入:S = {p1, . . . , pn}, n 二维平面上的点 每个点由其 x 和 y 坐标给出。

为简单起见，我们假设:

原点 (0, 0) 不在 S 中。
通过 (0, 0) 的任何直线 L 至多包含 S 中的一个点。
S 中没有三个点在同一条直线上。
如果我们从 S 中任意取三个点，我们就可以组成一个三角形。所以这样可以组成的三角形总数是Θ(n^3)。

有些三角形包含 (0, 0)，有些不包含。

问题:计算包含(0, 0)的三角形的个数。

您可以假设我们有一个时间复杂度为 O(1) 的函数 Test(pi, pj , pk) 给定 S 中的三个点 pi, pj , pk，如果三角形形成，则返回 1 by {pi, pj , pk} 包含 (0, 0)，否则返回 0。在 Θ(n^3) 时间内解决问题是微不足道的(只需枚举并测试所有三角形)。

描述一个用 O(n log n) 运行时间解决这个问题的算法。

---

我对上述问题的分析得出以下结论

有4个坐标(+,+),(+,-),(-,-),(-,+){x和y坐标是否>0}。

让

• s1 = 坐标 x < 0 和 y > 0
• s2 = x > 0 , y > 0
• s3 = x < 0 , y < 0
• s4 = x > 0 , y < 0

现在我们只需要对以下组合之间的点进行测试

1. S1 S2 S3
2. S1 S1 S4
3. S2 S2 S3
4. 中三中三中二
5. S1 S4 S4
6. 小一小三小四
7. 小一小二小四
8. 中二中三中四

我现在只需要测试上述集合组合中的点(例如来自 s1 的一个点，来自 s2 的一个点和来自 s3 的一个点)并通过调用查看包含 (0,0) 的点测试函数(这里假定为常数时间函数)。

有人可以指导我吗？

下面添加的图片用于说明为什么只有一些子集 (s1,s2, s4) 可以包含 (0,0) 而有些 (s1,s1,s3) 不能。

Answer 1

我猜我们在同一个类(class)(基于问题的奇怪措辞)，所以既然截止日期已经过去，我觉得可以给出我的解决方案。我设法找到了 n log n 算法，正如问题所述，它更多的是巧妙地转换问题，而不是动态编程/DaC 解决方案。

注意:这不是详尽的证明，我把它留给你。

---

首先，一些视觉观察。取一些明显包含原点的三角形。

然后，将点转换为向量。

说服自己，任意选择三个点，每个点取一个向量，描述一个也包含原点的三角形。

此外，如果您在不包含原点的三角形上执行上述步骤，则沿这些向量的点的任何组合也不包含原点。

从这里得到的要点是，矢量的大小无关紧要，重要的是方向。此外，对问题的提示说“任何线交叉(0 ,0) 只包含 S 中的一个点”，由此我们可以推断出每个向量的方向都是唯一的。

---

因此，如果只有角度很重要，那么可以得出一些逻辑来确定点的范围，给定两个点，可能形成一个包含原点的三角形。为简单起见，我们假设我们已获取 S 中的所有点并将它们转换为向量，然后对它们进行归一化，有效地使所有点位于单位圆上。

所以，沿着这个圆圈取两点。

然后，从每个点通过原点画一条线到圆的另一边。

由此得出，给定这两个点，任何位于红色圆弧上的点都可以形成一个三角形。

---

因此我们的算法应该执行以下操作:

1. 取 S 中的每个点。制作一个二级数​​组 A，并且对于每个点，将沿单位圆 (atan2(x,y)) 的角度添加到 A (0 ≤ Ai ≤ 2π)。我们假设这是 O(n)

2. 按递增方式对 A 排序。 O(n log n)，假设我们使用合并排序。

3. 计算每对 (Ai,Aj) 可能出现的三角形数量。这意味着我们计算 Ai + π ≤ Ak ≤ Aj + π 的数量。由于数组已排序，我们可以使用二进制搜索来查找 Ai + π 和 Aj + π 的索引，即 O(2 log n) = O(log n)

但是，我们遇到了一个问题，有 n^2 个点，如果我们必须对每个点进行 O(log n) 搜索，我们有 O(n^ 2 log n)。所以，我们需要再做一个观察。

给定一些 Ai < Aj，我们会说 Tij 描述了可能的三角形数，如上述方法所计算的那样。然后，给定第三个 Ak > Aj，我们知道 Tij ≤ Tik，因为 Ai + π 和 Ak + π 之间的点数必须至少与 Ai + π 和 Aj + π 之间的点数一样多。事实上，它就是 Ai + π 和 Aj + π 之间的计数，加上 Aj + π 和 Ak + π 之间的计数。由于我们已经知道 Ai + π 和 Aj + π 之间的计数，因此我们不需要重新计算它 - 我们只需要计算 Aj + π 和 Ak + π 之间的数，然后加上之前的计数。它遵循:

A(n) = count(A(n),A(n-1)) + count(A(n-1),A(n-2)) + ... + count(A(1) ,A(0))

这意味着我们不需要检查所有 n^2 对，我们只需要检查连续的对 - 所以，只有 n-1。

---

因此，以上所有可以为我们提供以下伪代码解决方案。

int triangleCount(point P[],int n)
    int A[n], C[n], totalCount = 0;  

    for(i=0...n)
        A[i] = atan2(P[i].x,P[i].y);

    mergeSort(A);

    int midPoint = binarySearch(A,π);

    for(i=0...midPoint-1)
        int left = A[i] + π, right = A[i+1] + π;
        C[i] = binarySearch(a,right) - binarySearch(a,left);
        for(j=0...i)
            totalCount += C[j]

return totalCount;