Maximum Area of a Triangle

Easy
0/40
Average time to solve is 10m
profile
Contributed by
22 upvotes
Asked in companies
BNY MellonAccoliteAmdocs

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample input 1
2
5
0 0
0 1
1 0
0 2
2 0
4
0 0
1 0
4 0
0 2
Sample Output 1
2.00000
4.00000
Explanation
Test case 1

The triangle with the maximum area will form by using [0, 0], [0, 2], and [2, 0] points.


The area will be 2 units.

Test case 2:

In this case, the triangle with the maximum area will form by using [0, 0], [4, 0], and [0, 2] points.


The area will be 4units.
Sample input 2:
2
5
0 0 
1 1 
5 0 
6 2
2 1
4
0 1
0 0 
0 2
0 6
Sample Input 2:
5.00000
0.00000
Explanation
In the second test case, all the points lie on the same line i.e. they are collinear so no triangle can be formed. Hence, the maximum area will be 0.
Hint

Can you think of a solution by checking the area of every possible triangle?

Approaches (1)
Brute force

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’.
Time Complexity

O(N^3), where N is the number of given points.

 

Since we are iterating through each possible triplet formed by the given points and so, the overall time complexity will be O(N^3).

Space Complexity

O(1).

 

No extra space is used.

Code Solution
(100% EXP penalty)
Maximum Area of a Triangle
Full screen
Console