查看“︁06-数学相关/06-计算几何”︁的源代码


== 欧几里得距离 ==

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

== 海伦公式 ==

三角形三边长分别为 <math>a,b,c</math>，定义半周长 <math>p=\frac{a+b+c}{2}</math>，则三角形面积为：

<math>S=\sqrt{p(p-a)(p-b)(p-c)}</math>

== 向量叉乘 ==

<math>\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>

意义：

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

<syntaxhighlight lang="cpp">
// 传入两个点，返回对应向量（第一个点指向第二个点）
pair<double, double> getV(pair<double, double> a, pair<double, double> b)
{
    return {b.first - a.first, b.second - a.second};
}

// 传入两个向量，返回叉乘结果
// 如果结果为正，第二个向量偏左，否则偏右
double getMul(pair<double, double> a, pair<double, double> b)
{
    return a.first * b.second - a.second * b.first;
}
</syntaxhighlight>

=== 三角形面积 ===

三角形 <math>ABC</math> 的面积：

<math>S=\frac{1}{2}|\vec{AB}\times \vec{AC}|</math>

== 线段相交判断 ==

对于四个点 <math>A,B,C,D</math>，判断线段 <math>AB</math> 与线段 <math>CD</math> 是否相交。

通过计算 <math>\vec{AB}\times \vec{AC}</math> 与 <math>\vec{AB}\times \vec{AD}</math>，如果结果一正一负，则 <math>C,D</math> 两点处于直线 <math>AB</math> 的两边。同理判断 <math>A,B</math> 是否在直线 <math>CD</math> 的两边。如果两个条件都满足，则两线段相交。

<syntaxhighlight lang="cpp">
bool checkX(pair<double, double> a, pair<double, double> b,
            pair<double, double> c, pair<double, double> d)
{
    double x, y;
    // c,d 是否在直线 ab 的两边
    auto AB = getV(a, b);
    auto AC = getV(a, c);
    auto AD = getV(a, d);
    x = getMul(AB, AC);
    y = getMul(AB, AD);
    if (x > 0 && y > 0 || x < 0 && y < 0) // c,d 在 ab 同一侧
        return false;
    // a,b 是否在直线 cd 的两边
    auto CD = getV(c, d);
    auto CA = getV(c, a);
    auto CB = getV(c, b);
    x = getMul(CD, CA);
    y = getMul(CD, CB);
    if (x * y > 0)
        return false;
    return true;
}
</syntaxhighlight>

== 常用几何模板速记 ==

{| class="wikitable"
! 功能 !! 公式/方法
|-
| 两点距离
| <math>\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}</math>
|-
| 叉乘
| <math>a_x b_y - a_y b_x</math>
|-
| 点积
| <math>a_x b_x + a_y b_y</math>
|-
| 三角形面积
| <math>\frac{1}{2}
| \vec{AB}\times \vec{AC}
| </math>
|-
| 向量夹角余弦
| <math>\frac{\vec{u}\cdot\vec{v}}{
| \vec{u}
| 
| \vec{v}
| }</math>
|}


[[Category:数学相关]]
[[Category:三三文档]]