The way I solved the problem was by first looking at the constraints.
Here the array provided to us would always have three elements and the each element of the array in turn would have two elements inside it. Each element of the array is a set of co-ordinate points on the X-Y plane. If we have three distinct points and connect three points, they generally form a triangle.
Given the coordinates of the three vertices of any triangle, the area of the triangle is given by:
Area of a triangle from co-ordinate points = | aX (bY-cY) + bX (cY-aY) + cX(aY-bY) /2 |
This formula allows you to calculate the area of a triangle when you know the coordinates of all three vertices. It does not matter which points are labelled A,B or C, and it will work with any triangle, including those where some or all coordinates are negative.
The two vertical bars mean “absolute value”. This means that it is always positive even if the formula produced a negative result. Polygons can never have a negative area.
How to know the points do not lie in a straight line?
If the area comes out to be zero, it means the three points are collinear. They lie in a straight line and do not form a triangle.
Since points is a 2d array, each inner array represents a point. I have taken six variables and assigned each element of the inner array to the variable. Each variable represents either the X coordinates or the Y coordinates. The first, second and the third element of the outer array corresponds to “a”, “b” and “c” respectively.
Then calculated area by applying the above equation.
Then put a conditional to check if the area is equal to zero. If the area is equal to zero return false else return true.
Since area is double, the right hand side of the conditional cannot be 0, it is either 0.0 or 0d.
The time complexity of the algorithm is O(1).