Valid Boomerang

Easy
0/40
Average time to solve is 10m
profile
Contributed by
1 upvote
Asked in company
Facebook

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
0 0
1 1
2 2
0 0
1 1
2 1
Sample Output 1 :
false
true
Explanation For Sample Input 1 :
Test Case 1 :
If you look at the graph, all three points are in a straight line.

altImage

Test Case 2 :
If you look at the graph, there is no straight line possible to pass through all three points.

altImage

Sample Input 2 :
2
4 0
4 5
2 1
2 2
2 4
2 6
Sample Output 2 :
true
false
Hint

Think of finding the area of a triangle.

Approaches (2)
Area Of The Triangle
  • 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.
Time Complexity

O(1).

 

As we are using only a variable to store the area of the triangle. Hence, the time complexity will be O(1).

Space Complexity

O(1).

 

As we are using constant extra space.

Code Solution
(100% EXP penalty)
Valid Boomerang
Full screen
Console