Approach #1: Brute Force [Accepted]

Intuition

For each possible triangle, check it's area and keep the area of the largest.

Algorithm

We will have 3 for loops to cycle through each choice of 3 points in the array.

After, we'll need a function to calculate the area given 3 points. Here we have some options:

  • We can use the Shoelace formula directly, which tells us the area given the 3 points;

  • We can use Heron's formula, which requires the 3 side lengths which we can get by taking the distance of two points;

  • We can use the formula area = 0.5 * a * b * sin(C) and calculate the angle C with trigonometry.

Our implementation illustrates the use of the shoelace formula.

If we did not know the shoelace formula, we could derive it for triangles with the following approach: starting with points (px, py), (qx, qy), (rx, ry), the area of this triangle is the same under a translation by (-rx, -ry), so that the points become (px-rx, py-ry), (qx-rx, qy-ry), (0, 0).

From there, we could draw a square around the triangle with sides touching the coordinate axes, and calculate the area of the square minus the area of the right triangles surrounding the inner triangle.

For more on this approach, see the Wikipedia entry for the Shoelace formula.

Complexity Analysis

  • Time Complexity: , where is the length of points. We use three for-loops of length , and our work calculating the area of a single triangle is .

  • Space Complexity: .


Analysis written by: @awice.