问题

给定一个三角形三个顶点的坐标，另给一个点的坐标，如何判断这个点在三角形的内部？

如下图所示：

仔细观察，会发现点S在图中所有有向线段的一侧（左侧）。实际上，当且仅当点处在三角形内部时，在所有边构成的有向线段的一侧（有向线段都顺时针或逆时针）。

To left test

那么问题就规约（reduction)为了如何判断一个点在一条有向线段的一侧。这里引入To left test。

我们知道三角形有向面积的计算公式如下：

$$
2*Area =
\left|\begin{matrix}
p_x & p_y & 1 \\
q_x & q_y & 1 \\
s_x & s_y & 1 \\
\end{matrix}\right|
$$

我们可以利用三角形有向面积的符号来判定一个点处在一条有向直线的左边还是右边。所以，我们只需要判断一个点与三角形三条边构成的三角形的有向面积的符号是否一致，就可以知道这个点是在三角形内部还是外部了。

$$
\left|\begin{matrix}
p_x & p_y & 1 \\
q_x & q_y & 1 \\
s_x & s_y & 1 \\
\end{matrix}\right|=p_x\times q_y-p_y\times q_x+q_x\times s_y-q_y\times s_x+s_x\times p_y-s_y\times p_x
$$