Last Updated: 16 Apr, 2021
Check If It Is a Straight Line
Easy
Asked in company
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.
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.
Approaches
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.
The idea is to use the slopes as criteria to check whether the given points lie in a straight line or not. From geometry, any pair of points lying in a straight line gives the same slope value.
The slope between two points (X0, Y0) and (X1, Y1) is (Y1 - Y0) / (X1 - X0).
So, for any third point: (X, Y). We have:
(Y1 - Y0) / (X1 - X0) = (Y - Y0) / (X - X0)
So, we have to check the above condition for every point. To avoid division by zero, the above condition can be rewritten as:
(Y1 - Y0) * (X - X0) = (X1 - X0) * (Y - Y0)
DY * (X - X0) = DX * (Y - Y0), where DX = X1 - X0 and DY = Y1 - Y0.
So, if the above condition becomes false for any point, then the given points will not lie in a straight line. Otherwise, all points will 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.
- Declare four integer variables, ‘X0’, ‘Y0’, ‘X1’ and ‘Y1’and assign them ‘POINTS[ 0 ][ 0 ]’, ‘POINTS[ 0 ][ 1 ]’, ‘POINTS[ 1 ][ 0 ]’ and ‘POINTS[ 1 ][ 1 ]’, respectively.
- Declare two integer variables, ‘DX’ and ‘DY’ and assign them ‘X1 - X0’ and ‘Y1 - Y0’, respectively.
- Run a loop for i = 2 to N.
- Declare two integer variables, ‘X’ and ‘Y’ and assign them ‘POINTS[ i ][ 0 ] and POINTS[ i ][ 1 ], respectively.
- If (DX * (Y - Y0) != DY * (X - X0)) that shows that slopes are not equal. Therefore,
- Return false.
- In the end, return true.
Since any straight line can be represented by the equation A * X + B * Y + C = 0, where A, B and C are real numbers. The idea is to find the values of the constants A, B and C. We can then substitute the X and Y coordinates of any point in the expression A * X + B * Y + C. If it evaluates to zero, then the given point lies in the straight line.
Finding the values of A, B and C using two points, (X0, Y0) and (X1, Y1):
The slope between two points (X0, Y0) and (X1, Y1) is, M = (Y1 - Y0) / (X1 - X0).
The equation A * X + B * Y + C = 0 can be rearranged in slope intercept form as:
Y = (-A / B) * X + (-C / B)
So, M = -A / B = (Y1 - Y0) / (X1 - X0). Therefore, A = Y0 - Y1 and B = X1 - X0.
And since (X0, Y0) lies in the line A * X + B * Y + C = 0.
We have, A * X0 + B * Y0 + C = 0. Therefore, C = -A * X0 - B * Y0.
Hence, A = Y0 - Y1, B = X1 - X0 and C = -A * X0 - B * Y0.
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.
- Declare four integer variables, ‘X0’, ‘Y0’, ‘X1’ and ‘Y1’and assign them ‘POINTS[ 0 ][ 0 ]’, ‘POINTS[ 0 ][ 1 ]’, ‘POINTS[ 1 ][ 0 ]’ and ‘POINTS[ 1 ][ 1 ]’, respectively.
- Declare three integer variables, ‘A’, ‘B’ and ‘C’ and assign them ‘Y0 - Y1’, ‘X1 - X0’ and ‘-A * X0 - B * Y0’, respectively.
- Run a loop for i = 2 to N.
- Declare two integer variables, ‘X’ and ‘Y’ and assign them ‘POINTS[ i ][ 0 ]’ and ‘POINTS[ i ][ 1 ]’, respectively.
- If ((A * X + B * Y + C) != 0) that shows that the given point does not lie on the straight line. Therefore,
- Return false.
- In the end, return true.
Similar problems