問題
N個の頂点が与えられる。これらの頂点を用いて内側に原点を含む三角形の数を求めよ。
解法
はじめに、三角形の総数Sを以下の式で計算する。
原点を含まない三角形の総数を求め、Sから引く。
原点を含まない三角形は、外積を用いて求める。まず、頂点iを選択し原点とのベクトルuを考える。残りの頂点jに対してのベクトルvとの外積を求め、正(または負)の値になる集合を求める。この集合から2つの頂点を選び、三角形を形成しても原点を含む事はない。集合の要素数をkとすると
個の頂点を含まない三角形が作れる。これを全頂点に行うことで答えが求まる。
計算量
