首先，归功于 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;
}
}
Let there be a triangle with 3 points p1=(x_1, y_1),p2=(x_2, y_2) and p3=(x_3, y_3). Let p1, p2, p3 be the position vectors. If the origin lies within, then cross product of any one position vector with other two will be different in sign (one negative, one positive). But if the origin lies outside, then there will be one point which has negative cross product with both the other points. So for each point i, find points whose cross product is less than 0. Now if you select any two of these points and make a triangle along with point i, the origin will be outside this triangle. That's why you subtract from res (selection of 2 from such points + point i). This was by far the best solution many implemented as it did not have the problem of precision with double etc.
