请教一个公式

在$\triangle ABC$中，已知$A$、$B$、$C$的坐标分别是$A(x_1,\,y_1)$、$B(x_2,\,y_2)$、$C(x_3,\,y_3)$。
在$\triangle ABC$ 所在的平面中，有一个点$P$，并已知其坐标为$P(x_0,\,y_0)$。

是否有一个公式，能直接判断$P$点是否在$\triangle ABC$内？
是否有一个公式，能直接判断$P$点是否在$\triangle ABC$的边上？
是否有一个公式，能直接判断$P$点是否在$\triangle ABC$外？

没研究过，想了一下不知用有向面积行不行？

PS、不必每处公式都加 \displaystyle 吧……

或者算 XA、XB、XC 两两夹角之和来判断？

线性规划

4# 海盗船长

具体怎么操作……

4# 海盗船长


写出约束条件代入？

这个问题有意思，我得到了一个结果，不过不能用一个公式那么简单，而是看三个式子的符号决定。
结果是这样的：
============================结果============================
三角形的三个顶点假定为 $A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)$ ，要判断的点是 $P(x_0,y_0)$，写出下面的三个表达式:
\[
\left|
\begin{array}{cc}
x_3-x_1 & x_2-x_1 \\
y_3-y_1 & y_2-y_1
\end{array}
\right|
\cdot
\left|
\begin{array}{cc}
x_0-x_1 & x_2-x_1 \\
y_0-y_1 & y_2-y_1
\end{array}
\right|
\]
以及
\[
\left|
\begin{array}{cc}
x_1-x_2 & x_2-x_3 \\
y_1-y_2 & y_2-y_3
\end{array}
\right|
\cdot
\left|
\begin{array}{cc}
x_0-x_2 & x_2-x_3 \\
y_0-y_2 & y_2-y_3
\end{array}
\right|
\]
与
\[
\left|
\begin{array}{cc}
x_2-x_3 & x_1-x_3 \\
y_2-y_3 & y_1-y_3
\end{array}
\right|
\cdot
\left|
\begin{array}{cc}
x_0-x_3 & x_1-x_3 \\
y_0-y_3 & y_1-y_3
\end{array}
\right|
\]
这里双竖线是行列式符号，可以简单的认为
\[
\left|
\begin{array}{cc}
a_{11} & a_{12} \\
a_{21} & a_{22}
\end{array}
\right|
=a_{11}a_{22}-a_{12}a_{21}
\]
根据这三个表达式的符号即可判断点 $P$ 的位置：
如果三个表达式全为正数，则点 $P$ 在三角形内
如果三个表达式中有两个为零，则点在三角形的边上，三个为零是不可能的。
如果三个表达式中有且只有一个为零，这时需要判断另外两个表达式的符号，如果均为正，则是在三角形的一条边上，若是一正一负，则是在一边的延长线上，即是在三角形外
如果三个表达式中有两正一负，则为三角形外
如果三个表达式中有两个负数，则为三角形外，不可能三个都是负数的，分析见后。
这就是结果，虽然可以把它们组合成一个式子来进行判别，但我觉得为了把它们组合成一个复杂表达式没啥意思，反而看不出来原理，所以这个结果我就已经满意了。
============================原理============================
现在说说它的原理，其实很简单，一条直线把平面会分成两半，两边的点代入直线的方程，它的符号是相反的，而直线上的点代入方程，它是等于0的。
如果点 $P$ 在三角形内，那么点 $P$与点 $A$ 位于直线 $BC$ 的同侧，$P$ 与 $B$ 位于直线 $AC$ 的同侧，$P$ 与 $C$ 位于直线 $AB$ 的同侧。
如果点 $P$ 在三角形上，那么点 $P$ 至少位于三条边中的一条上，当然也可能是两边，但是绝对不会同时位于三条边上，所以上面那三个表达式中最多有两个为零。
如果点 $P$ 在三角形外，那么画个图简单分析一下就可以得到上面的结果。

话说，上面这个结果尤其适合于程序实现

8# 都市侠影

话说，上面这个结果尤其适合于程序实现

话说这题就是编程题。

原题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=4380


输入n,m。
接下来n行，输入n个坐标，表示可选的坐标。
接下来m行，输入m个坐标，表示goldstones的坐标。

从n个可选的点中，选出三个点。这三个点必须围住奇数个goldstones。问点有几种选择法。

发现了一个 bug，如果点 $P$ 在三角形外，那三个表达式中也是有可能有一个为零的，这时点在边的延长线上。
已经在楼上修正

5# kuing


嗯，就是zhcosin的那个方法

这题还可以用“有向面积”来计算。

若$\triangle PAB$、$\triangle PBC$、$\triangle PCA$，三个三角形的有向面积同号，则点$P$在$\triangle ABC$内。
否则，若三个三角形的有向面积至少有一个等于0，则，点$P$在$\triangle ABC$的边上。
否则，点$P$在$\triangle ABC$外。






P.S.  

有向面积的定义：

已知$A(x_1,\,y_1)$、$B(x_2,\,y_2)$、$C(x_3,\,y_3)$，则$\triangle ABC$的有向面积是：
\[ \frac{1}{2}\left|\begin{array}{ccc}x_1 & y_1 & 1 \\x_2 & y_2 & 1 \\x_3 & y_3 & 1\end{array}\right| \]

有向面积的性质：

一个三角形的有向面积的绝对值，等于这个三角形的面积。
若$\triangle ABC$有向面积为正，则$A \longrightarrow B \longrightarrow C$正向绕行（即逆时针方向）。
若$\triangle ABC$有向面积为负，则$A \longrightarrow B \longrightarrow C$负向绕行（即顺时针方向）。

12# 叶剑飞Victor

嘻嘻…我第一反应就是有向面积   只是后来没细想了，懒了

12# 叶剑飞Victor
哈哈，你也犯了一个跟我一样的错误，当三个中有一个为零时，这个点也有可能是在边的延长线上，即是在三角形外。

或者算 XA、XB、XC 两两夹角之和来判断？
kuing 发表于 2012-8-22 16:15

这个没人写？那我来续一下吧……

输入 $A$、$B$、$C$、$X$ 的坐标；
计算 $S_{\triangle ABC}$ 并判断是否为 $0$，如果为 $0$，报错重新输入，否则继续；
令 $x=\overrightarrow{XA}$、$y=\overrightarrow{XB}$、$z=\overrightarrow{XC}$；
判断 $x$、$y$、$z$ 中是否有 $\overrightarrow0$，如果有，则报 $X$ 在三角形顶点上并结束，否则继续；
令 $\alpha=\arccos\dfrac{y\cdot z}{|y|\cdot |z|}$、$\beta=\arccos\dfrac{z\cdot x}{|z|\cdot |x|}$、$\gamma=\arccos\dfrac{x\cdot y}{|x|\cdot |y|}$；
判断 $\alpha$、$\beta$、$\gamma$ 中是否有 $0$，如果有，则报 $X$ 在三角形的边的延长线上，否则继续；
判断 $\alpha$、$\beta$、$\gamma$ 中是否有 $\pi$，如果有，则报 $X$ 在三角形的边上（不含顶点），否则继续；
判断 $\alpha+\beta+\gamma$ 是否等于 $\pi$，如果相等，则报 $X$ 在三角形内，否则报 $X$ 在三角形外并结束。

理论上是这样的，但这里用了 $\arccos$ 并且最后判断时还要与 $\pi$ 比较，可能容易产生误差……
这里其实还可以更细化地将具体在哪个顶点或哪条边上也给出。具体要翻译成计算机语言我就不懂了……

15# kuing

貌似凸N边形也可以这样玩

15# kuing

令 $x=\overrightarrow{XA}$、$y=\overrightarrow{XB}$、$z=\overrightarrow{XC}$

单个小写英文字母表示向量的时候，印刷体要用粗体字表示，例如$\boldsymbol{x}$；手写体要在上面写个箭号，例如$\overrightarrow{x}$。

17# 叶剑飞Victor

这我当然是知道的（see http://kkkkuingggg.5d6d.net/thread-69-1-1.html），只是我最近懒么，如果要打粗斜体的话，还不如不令，直接用两个字母的向量还省些输入量……

18# kuing


其实可以打“\vec x”（显示成$\vec x$），三个字母而已。
P.S. “\vec”就是vector（向量）的意思。

19# 叶剑飞Victor

这个我这里有点怪，\vec 在 firefox 里显示正常，用 IE 或 chrome 都会显示有问题，不知为什么。

IE：

(1.21 KB)

2012-8-23 17:09

chrome：

(1.22 KB)

2012-8-23 17:09

也不知别人的是不是这样，所以我一直就没用它。