题目链接

三角形面积

题目描述

给定平面上不共线的三个整数点，求这三个点构成的三角形的面积。

  • 题目以核心代码模式提供，你需要实现 getArea 函数。
  • 输入参数是一个 Triangle 对象，包含 a, b, c 三个 Point。
  • 返回值是一个 double 类型的浮点数。主函数会负责将其格式化为两位小数后输出。
  • 保证输入的三个点不共线。

示例: 输入: (0, 0) (0, 2) (1, 1) 输出: 1.00

解题思路

对于由三个坐标点 , , 构成的三角形，我们可以使用向量叉积或鞋带公式 (Shoelace Formula) 来计算其面积。这两种方法在本质上是等价的，并且对于整数坐标点来说非常高效和精确。

向量叉积法

  1. 选择一个顶点作为公共起点，例如点 。
  2. 构造两个从该点出发的向量：
  3. 这两个向量所张成的平行四边形的有向面积等于它们二维叉积的值：
  4. 三角形的面积是该平行四边形面积的一半。我们取其绝对值，因为面积不能为负。

鞋带公式

鞋带公式是上述方法的一个推广形式，看起来像这样：

两种方法都可以，但向量叉积的实现可能在代码上更直观一些。

算法步骤：

  1. 从输入的 Triangle 对象中提取出三个点的坐标。
  2. 根据向量叉积公式计算平行四边形的面积。
  3. 将结果除以 2.0 并返回。

代码

double getArea(triangle T){
    point pA = T.a;
    point pB = T.b;
    point pC = T.c;
    
    double cross_product = (pB.x - pA.x) * (pC.y - pA.y) - (pC.x - pA.x) * (pB.y - pA.y);
    
    return std::abs(cross_product) / 2.0;
}

static double getArea(Triangle T) {
    Point pA = T.a;
    Point pB = T.b;
    Point pC = T.c;

    double crossProduct = (pB.x - pA.x) * (pC.y - pA.y) - (pC.x - pA.x) * (pB.y - pA.y);

    return Math.abs(crossProduct) / 2.0;
}

def get_area(T: Triangle) -> float:
    pA = T.a
    pB = T.b
    pC = T.c
    
    cross_product = (pB.x - pA.x) * (pC.y - pA.y) - (pC.x - pA.x) * (pB.y - pA.y)
    
    return math.fabs(cross_product) / 2.0

算法及复杂度

  • 算法: 向量叉积/鞋带公式
  • 时间复杂度: 。该计算涉及固定数量的算术运算，与输入坐标的大小无关。
  • 空间复杂度: 。除了存储输入和几个临时变量外，没有使用额外的与输入规模相关的空间。