Calculate the area of triangle in algorithm question

In algorithm questions, knowing how to calculate the area of the triangle makes problems easy.

Leetcode 1037. Valid Boomerang

Leetcode 812. Largest Triangle Area

Calculate area

In an algorithm problem, we usually use (x, y) to represent a point in Cartesian coordinate system. Given three points, how can we calculate the area? we need to know the concept of Vector product firstly.

Vector product

As shown in the figure, the $|a \times b|$ represents the area of the parallelogram combined with Vector a and Vector b. If we just want to get the area of the triangle, it’s half.

How to calculate vector product?

Formula

Given 4 points:

$A(x_a,y_a) \ B(x_b, y_b) \ C(x_c,y_c) \ O(0,0)$

According to vector calculation, we know:

$\vec{AB}=\vec{AO} + \vec{OB} = \vec{OB} - \vec{OA} = ((x_b-x_a), (y_b-y_a))$

$\vec{AC} = \vec{OC} - \vec{OA} = ((x_c - x_a), (y_c - y_a))$

so the area of ABC:

$\Delta_{ABC}=1 / 2 \times | \vec{AB} \times \vec{AC} |$

and

$\vec{AB} \times \vec{AC} \\ = |(x_b - x_a) \times (y_c - y_a) - (y_b -y_a) \times (x_c - x_a)| \\ = |(x_a \times y_b + x_b \times y_c + x_c \times y_a) - (x_c \times y_b + x_b \times y_a - x_a \times y_c)|$