algorithm - 包含点 (0,0) 的三角形数

Question

首先，感谢 Topcoder，因为这个问题在他们的一个 SRM 中使用过(但他们没有关于它的社论......)

在这个问题中，我得到 n 分(其中 n 介于 1 和 1000 之间)。每三个点，显然都有一个三角形将它们连接起来。问题是，这些三角形中有多少包含点 (0,0)。

我试过在堆栈上查看这个线程:

triangle points around a point

但是我无法理解使用了什么数据结构/如何使用它们来解决这个问题。

这个问题的一个明显的幼稚解决方案是使用低效的 O(n^3) 算法并搜索所有点。但是，有人可以帮我提高效率，并在 O(n^2) 时间内完成吗？

下面是 Petr 对这个问题的解决方案......它很短，但有一个我无法理解的宏大想法。

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class TrianglesContainOrigin {
    public long count(int[] x, int[] y) {
        int n = x.length;
        long res = (long) n * (n - 1) * (n - 2) / 6;
        for (int i = 0; i < n; ++i) {
            int x0 = x[i];
            int y0 = y[i];
            long cnt = 0;
            for (int j = 0; j < n; ++j) {
                int x1 = x[j];
                int y1 = y[j];
                if (x0 * y1 - y0 * x1 < 0) {
                    ++cnt;
                }
            }
            res -= cnt * (cnt - 1) / 2;
        }
        return res;
    }
}

Answer 1

假设有一个包含 3 个点的三角形 p1=(x_1, y_1),p2=(x_2, y_2) 和 p3=(x_3, y_3 ) 。设 p1、p2、p3 为位置向量。如果原点在其中，则任何一个位置向量与其他两个位置向量的叉积符号不同(一负一正)。但是如果原点在外面，那么就会有一个点与其他两个点的叉积为负。因此，对于每个点 i，找到其叉积小于 0 的点。现在，如果您选择这些点中的任意两个并与点 i 一起构成一个三角形，则原点将在该三角形之外。这就是你从 res 中减去的原因(从这些点中选择 2 + 点 i)。这是迄今为止许多实现的最佳解决方案，因为它没有 double 等的精度问题。