欧几里得距离

• $(x_1,y_1)$ 与 $(x_2,y_2)$ 的距离为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$
• $(x_1,y_1,z_1)$ 与 $(x_2,y_2,z_2)$ 的距离为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$

海伦公式

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

$S=\sqrt{p(p-a)(p-b)(p-c)}$

向量叉乘

\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

意义：

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

// 传入两个点，返回对应向量（第一个点指向第二个点）
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;
}

三角形面积

三角形 $ABC$ 的面积：

$S=\frac{1}{2}|\vec{AB}\times \vec{AC}|$

线段相交判断

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

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

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;
}

常用几何模板速记