[AOJ] No. 0035 Is it Convex?

Is it Convex?

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0035

考え方

題意

与えられた座標を元にした四角形が凹んでいるかどうかを調べます。凹んでいる四角形は、\( 90 \) 度よりも大きい内角を持つ四角形です。

方針

凹んでいる四角形の性質を考えると、任意の \( 3\) 点を頂点とする三角形に残りの点が内部に存在することが分かります。従って、三角形の内部に点が存在するかどうかを調べるには外積を計算すれば良いです。

コード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする