包含点的三角形数量（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为位置向量。如果原点位于其中，则任意一个位置向量与其他两个向量的叉积在符号上将是不同的（一个负值，一个正值）。但是如果原点在外，那么会有一个点与其他点都有负相关的交叉积。因此，对于每个点，我找到交叉积小于0的点。现在，如果选择这些点中的任意两点并与点i一起形成三角形，则原点将位于此三角形之外。这就是为什么从res中减去（选择2从这些点+点i）。这是迄今为止许多实施的最佳解决方案，因为它没有双精度等问题。