No.622

ベクトルの外積を計算する.

$$\begin{align} \vec{v_1} &= \overrightarrow{DA} \times \overrightarrow{DB} \\ \vec{v_2} &= \overrightarrow{DB} \times \overrightarrow{DC} \\ \vec{v_3} &= \overrightarrow{DC} \times \overrightarrow{DA} \\ \vec{u} &= \overrightarrow{AB} \times \overrightarrow{AC} \end{align}$$

次にベクトルの内積を計算する.

$$\begin{align} p_1 &= \vec{v_1} \cdot \vec{u} \\ p_2 &= \vec{v_2} \cdot \vec{u} \\ p_3 &= \vec{v_3} \cdot \vec{u} \\ \end{align}$$

$p_1, p_2, p_3$ がすべて正かすべて負であれば点 $D$ は三角柱の内部にある.

掛け算が4回なので long でもオーバーフローするので, BigInt を使う.