计算几何

欧几里得距离

• [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]

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

意义：

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

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

线段相交判断

对于四个点 [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] 的两边。

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

// 判断两个线段是否相交（ab ~ 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 的两边
    pair<double, double> AB = getV(a, b);
    pair<double, double> AC = getV(a, c);
    pair<double, double> 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 的两边
    pair<double, double> CD = getV(c, d);
    pair<double, double> CA = getV(c, a);
    pair<double, double> CB = getV(c, b);
    x = getMul(CD, CA);
    y = getMul(CD, CB);
    if (x * y > 0)
        return false;
    return true;
}