Last Updated: 14 Apr, 2021

Maximum Area of a Triangle

Easy

Asked in companies

Solve now

Problem statement

You are given 2D array/list 'POINTS' containing N distinct points on a 2D coordinate system where 'POINTS[i] = [Xi, Yi]. You have to find the maximum area of the triangle that can be formed by using any 3 points out of these N points.

Example

Let 'N' = 5, and the 'POINTS' = [ [0, 0], [2, 1], [0, 4], [0, 2], [5, 0] ].

Here, the maximum area triangle will be formed by using the points [0, 0], [0, 4], [5, 0] as shown below.

Hence, the area will be 10 units.

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains a single integer ‘N’ denoting the number of points given.

The next 'N' lines contain two single space-separated integers denoting the points in the 2D coordinate system.

Output Format

For each test case, return the maximum area of the triangle possible.

Note:

You don’t need to print anything or take input. This already has been taken care of. Just implement the function.

Constraints

1 <= T <= 10
3 <= N <= 100
-50 <= POINTS[i][0], POINTS[i][1] <= 50

Time limit: 1 sec

Solve now

Approaches

01 Approach

We will calculate the area of each possible triangle and then just take the maximum between them.

The formula for finding the area of a triangle formed by the points (x1, y1), (x2, y2),(x3, y3) is given below:

'AREA' = 0.5 * |x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)|

Algorithm:

Initialize a variable double ‘ANS’ = 0, to store the answer.
Iterate ‘i’ from 0 to ‘N’.
- Iterate ‘j’ from ‘i’ to ‘N’.
  - Iterate ‘k’ from ‘j’ to ‘N’.
  - Find the area of the triangle using the way mentioned above and store the result in a variable named ‘AREA’.
  - Here we will be checking all the triangle that can be formed so our points will be :
    - ‘X1’ = POINTS[i][0]
    - ‘X2’ = POINTS[j][0]
    - ‘X3’ = POINTS[k][0]
    - ‘Y1’ = POINTS[i][1]
    - ‘Y2’ = POINTS[j][1]
    - ‘Y3’ = POINTS[k][1]

Store the maximum between ‘ANS’ and ‘AREA’ in the ‘ANS’.
Return ‘ANS’.

Solve now