Check If It Is a Straight Line

Easy
0/40
Average time to solve is 20m
profile
Contributed by
14 upvotes
Asked in company
HCL Technologies

Problem statement

This time, Ninja was sent on a mission to hide ‘N’ mysterious gems on the ground with a condition to place all of them in a straight line. Ninja prepared a list of coordinates during the mission, ‘POINTS’, where he hides the gems. Your task is to return true if Ninja successfully hides all the gems in a straight line, otherwise return false.

For example:

Given POINTS = {{0, 0}, {1, 1}, {2, 2}}. Gems placed at coordinates (0, 0), (1, 1) and (2, 2) will lie in a straight line. Therefore, Ninja is successful in his mission.

Note:

POINTS[ i ] = {X, Y}, where ‘X’ and ‘Y’ represent the X and Y coordinates of a point, respectively, in a 2 - D plane.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains an integer ‘N’ representing the number of points.

The next ‘N’ lines of each test case contain two space-separated integers, ‘X and ‘Y’, representing the X and Y coordinates of a point, respectively.

Output Format:

For each test case, print a single line containing "true" if Ninja successfully hides all the gems in a straight line. Otherwise, print "false".

The output of 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 <= 5
2 <= N <= 1000
10 ^ -4 <= X, Y <= 10 ^ 4
|POINTS[ i ]| = 2
All points are distinct.

Where ‘T’ is the number of test cases, ‘N’ is the number of points in the ‘POINTS’ array, ‘X’, ‘Y’ are the X and Y coordinates of a point, respectively, and |POINTS[ i ]| is the length of the ‘i’th element of the ‘POINTS’ array.

Time limit: 1 sec.

Sample Input 1:

2
4
0 0
1 1
2 2
3 3
3
1 2
1 4
5 2

Sample Output 1:

true
false

Explanation of Sample Output 1:

Test Case 1 :  


As seen in the graph, all four points lie in a straight line. Hence, the output is true.

Test Case 2 :


Since all points do not lie in a straight line, the output is false.

Sample Input 2:

2
2
1 2
-10 4
4
1 2
1 18
1 -400
1 0

Sample Output 2:

true
true
Hint

Use the collinearity method.

Approaches (3)
Collinearity Method

The idea is to use the method of collinearity. Since two points will always be collinear, there is no need to check collinearity for two points.

Also, any three points: (X1, Y1), (X2, Y2) and (X3, Y3) will be collinear if and only if the area of the triangle formed by these points is 0, i.e.,

0.5 * (X1 * (Y2 - Y3) + X2 * (Y3 - Y1) + X3 (Y1 - Y2)) = 0.

So, we will evaluate the above expression for every three points. At any instant, the above expression gives a non zero result; it implies that the points are not collinear. Hence, do not lie in a straight line.

If all the points are collinear, then they all lie in a straight line.

 

Algorithm:

  • If N == 2, that shows that there are only two points. Since two points will always lie in a straight line. Therefore,
    • Return true.
  • Run a loop for i = 0 to N - 3.
    • Declare three vector of integers, ‘POINT1’, ‘POINT2’ and ‘POINT3’ and assign them ‘POINTS[ i ]’, ‘POINTS[ i + 1 ]’ and ‘POINTS[ i + 2 ]’, respectively.
    • Call ‘isCollinear’ function with ‘POINT1’, ‘POINT2’ and ‘POINT3’ as parameters. If ‘isCollinear’ function returns false, that shows that given points are not collinear. Therefore,
      • Return false.
  • In the end, return true.

 

Description of ‘isCollinear’ function

This function will take three parameters:

  • P1: A vector of integers to store ‘POINT1’.
  • P2: A vector of integers to store ‘POINT2’.
  • P3: A vector of integers to store ‘POINT3’.

bool isCollinear(P1, P2, P3):

  • Declare six integer variables, ‘X1’, ‘Y1’, ‘X2’, ‘Y2’, ‘X3’ and ‘Y3’ and assign them ‘P1[ 0 ], P1[ 1 ], P2[ 0 ], P2[ 1 ], P3[ 0 ] and P3[ 1 ], respectively.
  • If (X1 * (Y2 - Y3) + X2 * (Y3 - Y1) + X3 (Y1 - Y2)) != 0 that shows that given three points are not collinear. Therefore,
    • Return false.
  • In the end, return true.
Time Complexity

O(N), where ‘N’ is the number of points in the ‘POINTS’ array.

 

Since the loop runs ‘N’ times to process all the points.

Space Complexity

O(1).

 

Since no auxiliary space has been required.

Code Solution
(100% EXP penalty)
Check If It Is a Straight Line
Full screen
Console