C - Convex Quadrilateral Editorial by kyopro_friends


実は次が成り立ちます:
異なる \(2\)\(A=(A_x,A_y),B=(B_x,B_y)\) に対し、\(\angle AOB\) は、\(A_xB_y-A_yB_x>0\) のとき \(180\) 度未満であり、\(\leq 0\) のとき \(180\) 度以上である。ただし、角度は反時計回りに測るものとする。

このことの証明は、外積(cross product)を用いるのが一般的です。

外積について 外積の定義:
$3$ 次元空間内の $2$ つのベクトル $a,b$ の外積 $a\times b$とは、$a,b$ の両方に垂直で、右ねじの向き(図参照)を持ち、$a,b$ のなす平行四辺形の面積に等しい大きさを持つベクトルである。

(画像はwikipediaより引用)
外積の性質:
$a=(a_1,a_2,a_3),b=(b_1,b_2,b_3)$ としたとき、$a\times b=(a_2b_3-a_3b_2,a_3b_1-a_1b_3,a_1b_2-a_2b_1)$ である。
外積の性質から、$2$ 点 $(A_x,A_y,0),(B_x,B_y,0)$ について考えると冒頭の主張が得られます。

この事実を用いると、以下のように \(C-B\)\(A-B\) を用いて、角 \(B\) の大きさが \(180\) 度未満であるかどうかを判定することができます。

別の方法として、\(B-A\)\(C-B\) により判定することもできます。

posted:
last update: