计算几何

欧几里得距离

• [math]\displaystyle{ (x_1,y_1) }[/math] 与 [math]\displaystyle{ (x_2,y_2) }[/math] 的距离为 [math]\displaystyle{ \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} }[/math]
• [math]\displaystyle{ (x_1,y_1,z_1) }[/math] 与 [math]\displaystyle{ (x_2,y_2,z_2) }[/math] 的距离为 [math]\displaystyle{ \sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2} }[/math]

海伦公式

三角形三边长分别为 [math]\displaystyle{ a,b,c }[/math]，那么定义半周长 [math]\displaystyle{ p=\frac{a+b+c}{2} }[/math]

则三角形面积为 [math]\displaystyle{ \sqrt{p(p-a)(p-b)(p-c)} }[/math]

向量叉乘

[math]\displaystyle{ \vec{a}=(a_x,a_y),\ \vec{b}=(b_x,b_y) \quad\Rightarrow\quad \vec{a} \times \vec{b} = a_x b_y - a_y b_x }[/math]

实际上有三维上的意义，但是信息学竞赛中一般只关注上面式子的值。

意义：

• 结果的绝对值恰好为两向量为邻边的平行四边形的面积，因此可以用来计算三角形面积。
• 可以利用正负值判断两个向量的位置关系。

线段相交判断

对于四个点 [math]\displaystyle{ A,B,C,D }[/math]，判断线段 [math]\displaystyle{ AB }[/math] 与线段 [math]\displaystyle{ CD }[/math] 是否相交。

通过计算 [math]\displaystyle{ \vec{AB}\times \vec{AC} }[/math] 与 [math]\displaystyle{ \vec{AB}\times \vec{AD} }[/math]，如果结果一正一负，则 [math]\displaystyle{ C,D }[/math] 两点处于直线 [math]\displaystyle{ AB }[/math] 的两边。

同理可以判断[math]\displaystyle{ A,B }[/math] 两点是否处于直线 [math]\displaystyle{ CD }[/math] 的两边。

显然如果两个条件都满足，那么两线段相交。