Last Updated: 12 Apr, 2021
Valid Boomerang
Easy
Asked in company
You are given an array of ‘POINTS’ in a 2-D cartesian plane, where “POINTS[i] = [Xi, Yi]”, in which ‘Xi’ denotes the x-coordinate of the ‘i’th point, and ‘Yi’ denotes the y-coordinate of the ‘i’th point.
Let’s define the term ‘Boomerang’ as the set of three distinct points that are not in a straight line. Your task is to find out whether these points are a “boomerang” or not.
Note :
1. The size of the array ‘POINTS’ is always ‘3’.
2. For better understanding, you may look at the sample test cases.
Input Format :
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The next ‘3’ line of each test case contains two positive integers, ‘Xi’, and ‘Yi’, denoting the x and y coordinates of the ith point.
Output Format :
For each test case, print ‘true’ if the given points are a “boomerang”. Otherwise, print ‘false’.
Output for each test case will be printed in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10^5
POINTS.length == 3
POINTS[i].length == 2
-100 <= ‘Xi’, ‘Yi’ <= 100
Where ‘POINTS’ is an array of points, ‘Xi’ and ‘Yi’ are the i-th point’s x and y coordinates.
Time Limit: 1sec
Approaches
- For simplicity, let’s name the points as ‘P’, ‘Q’, and ‘R’.
- The idea here is to find the area of a triangle formed by the points P, Q, and R.
- If the area is zero, then these points are in a straight line. Otherwise, they are not in a straight line.
- For calculating the area we can use Heron's formula or otherwise the area can also be calculated by this formula, 1/2 [Px(Qy-Ry)+Qx(Ry-Py)+Rx(Py-Qy)].
- Here ‘Px’ is the x coordinate of the point ‘P’ and ‘Py’ is the y coordinate of the point ‘P’. Similarly for other points ‘R’, and ‘S’.
- So, if the area is non-zero then we return true. Else, return false.
- The idea here is to use the concept of slopes of the lines.
- For simplicity, let’s name the points as ‘P’, ‘Q’, and ‘R’.
- For any two lines, let it be ‘PQ’ and ‘PR’, can we form a relation between their slopes? Yes, we can.
- If the slope of the lines PQ, and PR are the same, then the points ‘P’, ’Q’, and ‘R’ are in a straight line. Otherwise, they are not in a straight line.
- The slope of the line PQ, slope1 = (points[0][1] - points[1][1]) / (points[0][0] - points[1][0]).
- The slope of the line PR, slope2 = (points[0][1] - points[2][1]) / (points[0][0] - points[2][0]).
- Formally, if slope1 != slope2, return true. Else, return false.
- An Implementation tip: To get rid of fractions, we can use cross multiplication.