AtCoder Beginner Contest 224 C 問題 Triangle?
問題
提出解答
問題の概要
座標平面上に 個の点があり,
番目の座標は
である.
個の点で
個選ぶ方法のうち, その
点を頂点とする三角形が正の面積を持つのは何通りか?
制約
個の点は相異なる.
解法
一般的に, 3点 を頂点とする三角形の面積は,
としたとき,
である. よって, 三角形 が正の面積を持つことと,
であることは同値である.
よって, 全ての取り出し方において, 上のようにして正の面積を持つかどうかを判定でき, 判定は , 組み合わせは
通りなので, 全体の計算量は
であり,
の制約下では高速である.