首先，要归功于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;
    }
}