Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 224 C 問題 Triangle?

AtCoder ABC ABC224 C問題 300 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

座標平面上に N 個の点があり, i 番目の座標は (X_i, Y_i) である. N 個の点で 3 個選ぶ方法のうち, その 3 点を頂点とする三角形が正の面積を持つのは何通りか?

制約

  • 3 \leq N \leq 300
  • -10^9 \leq X_i, Y_i \leq 10^9
  • N 個の点は相異なる.

解法

一般的に, 3点 A=(a_x, a_y), B=(b_x, b_y), C=(c_x,c_y) を頂点とする三角形の面積は, \boldsymbol{u} =(u_x,u_y)=\overrightarrow{AB}, \boldsymbol{v} =(v_x, v_y)=\overrightarrow{AC} としたとき,

\dfrac{1}{2} |u_x v_y-u_yv_x|

である. よって, 三角形 ABC が正の面積を持つことと, u_x v_y-u_yv_x=0 であることは同値である.

よって, 全ての取り出し方において, 上のようにして正の面積を持つかどうかを判定でき, 判定は O(1), 組み合わせは O(N^3) 通りなので, 全体の計算量は O(N^3) であり, N \leq 300 の制約下では高速である.