题解 | #点到直线距离#

题目链接

点到直线距离

题目描述

给定一个点 $P(x_p, y_p)$ 和一条由另外两个不同点 $P_A(x_A, y_A)$ 与 $P_B(x_B, y_B)$ 所确定的直线 $L$ ，你需要计算点 $P$ 到直线 $L$ 的垂直距离。

题目以核心代码模式提供，你需要实现 getDistance 函数。
输入参数为一个点 P 和一条线 L。
返回值是一个 double 类型的浮点数。主函数会负责将其格式化为两位小数后输出。

示例: 输入: P = (0, 0) L 由 (-1, 1) 和 (1, 1) 定义输出: 1.00

解题思路

这是一个经典的计算几何问题。计算点到直线的距离，最直接的方法是使用点到直线距离公式。

首先，我们需要根据直线上的两个点 $P_A(x_A, y_A)$ 和 $P_B(x_B, y_B)$ 推导出直线的一般式方程 $Ax + By + C = 0$ 。

$A = y_A - y_B$
$B = x_B - x_A$
$C = x_A y_B - x_B y_A$

得到直线方程后，点 $P(x_p, y_p)$ 到该直线的距离 $d$ 可以通过以下公式计算： $d = \frac{|A x_p + B y_p + C|}{\sqrt{A^2 + B^2}}$

从几何上理解：

分母 $\sqrt{A^2 + B^2}$ 正是点 $P_A$ 和 $P_B$ 之间的距离。
分子 $|A x_p + B y_p + C|$ 是由点 $P, P_A, P_B$ 构成的三角形面积的两倍。
因此，整个公式相当于 $\frac{2 \times \text{Area}}{\text{Base}}$ ，即三角形的高，也就是点到直线的距离。

特殊情况处理：如果 $P_A$ 和 $P_B$ 是同一个点，那么它们无法确定一条唯一的直线。此时，分母 $\sqrt{A^2 + B^2}$ 会为零。在这种情况下，问题就退化为计算点 $P$ 到点 $P_A$ 的距离。

算法步骤：

从输入参数中提取出三个点的坐标。
根据 $P_A$ 和 $P_B$ 的坐标计算出直线方程的系数 $A, B, C$ 。
计算分母，即 $P_A$ 和 $P_B$ 之间的距离。如果为 0，则直接计算并返回 $P$ 到 $P_A$ 的距离。
否则，计算分子 $|A x_p + B y_p + C|$ 。
返回分子 / 分母的结果。

代码

cpp
java
python

double getDistance(point P, line L){
    double xp = P.x, yp = P.y;
    double xA = L.point_A.x, yA = L.point_A.y;
    double xB = L.point_B.x, yB = L.point_B.y;

    double line_dist = hypot(xA - xB, yA - yB);

    // 如果定义直线的两点重合，则退化为点到点的距离
    if (line_dist == 0) {
        return hypot(xp - xA, yp - yA);
    }
    
    double A = yA - yB;
    double B = xB - xA;
    double C = xA * yB - xB * yA;
    
    double numerator = abs(A * xp + B * yp + C);
    
    return numerator / line_dist;
}

static double getDistance(Point P, Line L) {
    double xp = P.x, yp = P.y;
    double xA = L.pointA.x, yA = L.pointA.y;
    double xB = L.pointB.x, yB = L.pointB.y;

    double lineDist = Math.hypot(xA - xB, yA - yB);

    // 如果定义直线的两点重合，则退化为点到点的距离
    if (lineDist == 0) {
        return Math.hypot(xp - xA, yp - yA);
    }

    double A = yA - yB;
    double B = xB - xA;
    double C = xA * yB - xB * yA;
    
    double numerator = Math.abs(A * xp + B * yp + C);

    return numerator / lineDist;
}

def get_distance(P: Point, L: Line) -> float:
    xp, yp = P.x, P.y
    xA, yA = L.point_a.x, L.point_a.y
    xB, yB = L.point_b.x, L.point_b.y

    line_dist = math.hypot(xA - xB, yA - yB)

    # 如果定义直线的两点重合，则退化为点到点的距离
    if line_dist == 0:
        return math.hypot(xp - xA, yp - yA)
    
    # 使用叉积计算三角形面积的两倍，即平行四边形面积
    # Area = |(xp-xA)*(yB-yA) - (yp-yA)*(xB-xA)|
    # 这是向量 (P-A) 和 (B-A) 的叉积的绝对值
    numerator = math.fabs((xp - xA) * (yB - yA) - (yp - yA) * (xB - xA))

    return numerator / line_dist

算法及复杂度

算法: 点到直线距离公式（或向量叉积法）
时间复杂度: $\mathcal{O}(1)$ 。该计算涉及固定数量的算术运算，与输入坐标的大小无关。
空间复杂度: $\mathcal{O}(1)$ 。除了存储输入和几个临时变量外，没有使用额外的与输入规模相关的空间。