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

Question

首先,对Topcoder的信用,因为这个问题在他们的一个SRM中使用(但他们没有编辑...)

在这个问题中,我给了n个点(其中n在1到1000之间).对于每三个点,显然有一个连接它们的三角形.问题是,这些三角形中有多少包含点(0,0).

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

一个点周围的三角形点

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

这个问题的一个明显天真的解决方案是使用低效的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为位置向量.如果原点位于其中,那么任何一个位置向量与其他两个位置向量的交叉乘积将在符号上不同(一个负数,一个正数).但如果原点位于外面,则会有一个点与其他点都有负交叉积.因此,对于每个点,我找到交叉乘积小于0的点.现在,如果你选择这两个点中的任何两个并且与点i一起形成一个三角形,则原点将在该三角形之外.这就是为什么你从res中减去(选择2)从这些点+点i).这是迄今为止许多实施的最佳解决方案,因为它没有双精度等问题.