きままにものづくり

日々の気付いたことなんかを書いてます。

SRM641Div1Easy

問題

N個の頂点が与えられる。これらの頂点を用いて内側に原点を含む三角形の数を求めよ。

解法

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

計算量

 O(N^2)

コード

広告を非表示にする