包含點的三角形數量（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）。這是迄今爲止許多實施的最佳解決方案，因爲它沒有雙精度等問題。