Ninja And Geometry
Ninja has been given 2 points ‘A’ and ’B’ that corresponds to the line ‘AB’ and ‘P’, ’Q’ that corresponds to line ‘PQ’ on a 2D plane. Ninja wants to find the intersection point of the ‘AB’ and ‘PQ’ lines up to 6 decimal places. If there is no such intersection point print -1.000000 -1.000000.

Note:

1. You do not need to fix the output up to 6 decimal places. it has already been taken care of. Just return the output in the data type mentioned in the function. 2. Lines ‘AB’ and ‘PQ’ are two different lines.

For Example: For A(0, 3), B(3, 0) and P(0, 0), Q(5, 5) the point of intersection of line ‘AB’ and ‘PQ’ is (1.500000, 1.500000). As shown below:

As Ninja is weak in Geometry, can you help him to find the intersection of these two lines?

Input Format

The first line of input contains an integer ’T’ which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains 8 single space-separated integers ‘AX1’,’ AY1’, ’BX2’, ’BY2’, ’PX1’, ’PY1’, ’QX2’, ’QY2’ where ’AX1’ represents the ‘X’ coordinate of the point ‘A’ and ‘AY1’ represents the ‘Y’ coordinate of the point ‘A’ and so on.

Output Format :

For each test case, print the ‘X’ and ‘Y’ coordinates of the point of intersection of the two lines ‘AB’ and ‘PQ’ up to 6 decimal places. Print the output of each test case 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

Question

Ninja And Geometry

Ninja has been given 2 points ‘A’ and ’B’ that corresponds to the line ‘AB’ and ‘P’, ’Q’ that corresponds to line ‘PQ’ on a 2D plane. Ninja wants to find the intersection point of the ‘AB’ and ‘PQ’ lines up to 6 decimal places. If there is no such intersection point print -1.000000 -1.000000.

Note:

1. You do not need to fix the output up to 6 decimal places. it has already been taken care of. Just return the output in the data type mentioned in the function. 
2. Lines ‘AB’ and ‘PQ’ are two different lines.

For Example: For A(0, 3), B(3, 0) and P(0, 0), Q(5, 5) the point of intersection of line ‘AB’ and ‘PQ’ is (1.500000, 1.500000). As shown below:

alt

As Ninja is weak in Geometry, can you help him to find the intersection of these two lines?

Input Format

The first line of input contains an integer ’T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains 8 single space-separated integers ‘AX1’,’ AY1’, ’BX2’, ’BY2’, ’PX1’, ’PY1’, ’QX2’, ’QY2’ where ’AX1’ represents the ‘X’ coordinate of the point ‘A’ and ‘AY1’ represents the ‘Y’ coordinate of the point ‘A’ and so on.

Output Format :

For each test case, print the ‘X’ and ‘Y’ coordinates of the point of intersection of the two lines ‘AB’  and ‘PQ’ up to 6 decimal places. 

Print the output of each test case 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^2
1 <= ‘N’ <= 5*10^3
1 <= ‘AX1’, ’AY1’, ’BX2’, ’BY2’, ’PX1’, ’PY1’, ’QX2’, ’QY2’ <= 10^5 

Where ‘T’ denotes the total number of test cases, ‘N’ represents the number of boxes, ‘AX1’, ’AY1’, ’BX2’, ’BY2’, ’PX1’, ’PY1’, ’QX2’, ’QY2’ represents the the ‘X’ coordinate of the point ‘A’ and ‘AY1’ represents the ‘Y’ coordinate of the point ‘A’ and so on.

Time Limit: 1 sec

Accepted Answer

Mathematics

The idea behind this approach is to derive the equation of both of the lines ‘AB’ and ‘PQ’ and check if the Slope of these two lines is equal or not. Following are the two cases:

If the slope of ‘AB’ and ‘PQ’ is the same that means they are parallel so we return -1.
Else there must a point where ‘AB’ and ‘PQ’ are intersecting.

For a better understanding of this approach, Assume that we have two points which are A(a1, b1) and B(a2, b2). Now, we have to find the equation of line formed by points ‘A’ and ‘B’.

The equation of a line in geometry is :
a1(X) + b1(Y) = c1 (equation 1)
a2(X) + b2(Y) = c2 (equation 2)

Now we have to solve these 2 equations to get the point of intersection of these two lines. To solve this problem, we can multiply equation 1 by b2 and equation 2 by b1,this gives us the following result:

a1b2(X) + b1b2(Y) = c1b2 (equation 1)
a2b1(X) + b2b1(Y) = c2b1 (equation 2)
Subtracting equation 2 from equation 1 we get the following result:
- (a1b2 – a2b1) (X) = c1b2 – c2b1 (equation 3)
This can give us the value of X. Similarly, we can find out the value of the Y.So (X, Y) is the point of intersection of these two lines.
- If the coefficient of X in equation 3 is 0 that means lines the parallel. because in that case the equation becomes invalid and (a1b2 – a2b1) represents the difference between the slopes of the two lines.
- ‘slopeDiff’ = a1 b2 - a2 b1

Here is the complete algorithm:

Find the difference between the slopes of the two lines i.e. ‘slopeDiff’ = ‘a1’ * ‘ b2’ - ‘a2’ * ‘ b1’
If ‘slopeDiff’ is 0 that means lines are parallel. Return -1.
Else following are the two cases:
- The ‘X’ coordinate of the point of the intersection is (‘c1’ * ‘b2’ - ‘c2’ * ‘b1’) / ‘slopeDiff’.
- The ‘Y’ coordinate of the point of the intersection is (‘a1’ * ‘c2’ - ‘a2’ * ‘c1’) / ‘slopeDiff’
Finally, insert these coordinates into an array/list and return the array/list.

Space Complexity: O(1)Explanation:

O(1).

Because we are not using any extra space. Hence the overall space complexity will be O(1).

Time Complexity: O(1)Explanation:

O(1).

Because we are computation results from the given coordinates using binary operators. Hence overall time complexity will be O(1).

Java (SE 1.8)

/*
 	Time Complexity : O(1)
	Space Complexity : O(1)
*/

import java.util.ArrayList;

public class Solution {
	public static ArrayList findIntersection(double ax1, double ay1, double bx1, double by1,
	double px2, double py2, double qx2,
	double qy2) {	
        
        ArrayList answer = new ArrayList();
        // Line AB will be represented as a1x + b1y = c1.
        double a1 = by1 - ay1;
        double b1 = ax1 - bx1;
        double c1 = (a1 * ax1) + (b1 * ay1);

        // Line CD will be represented as a2x + b2y = c2.
        double a2 = (qy2 - py2);
        double b2 = (px2 - qx2);
        double c2 = (a2 * px2) + (b2 * py2);

        double slopeDiff = (a1 * b2) - (a2 * b1);

        if (slopeDiff == 0) {
            answer.add(-1d);
            answer.add(-1d);
        } else {
            double x = (b2 * c1 - b1 * c2) / slopeDiff;
            double y = (a1 * c2 - a2 * c1) / slopeDiff;
            answer.add(x);
            answer.add(y);
        }

        return answer;
        
    }
}

C++ (g++ 5.4)

/*
    Time Complexity : O(1)
    Space Complexity : O(1)
*/

vector findIntersection(double ax1, double ay1, double bx1, double by1,
                                double px2, double py2, double qx2,
                                double qy2) {
    vector answer;
    // Line AB will be represented as a1x + b1y = c1.
    double a1 = by1 - ay1;
    double b1 = ax1 - bx1;
    double c1 = a1 * ax1 + b1 * ay1;

    // Line CD will be represented as a2x + b2y = c2.
    double a2 = qy2 - py2;
    double b2 = px2 - qx2;
    double c2 = a2 * px2 + b2 * py2;

    double slopeDiff = a1 * b2 - a2 * b1;

    if (slopeDiff == 0) {
        answer = {-1, -1};
    } else {
        double x = (b2 * c1 - b1 * c2) / slopeDiff;
        double y = (a1 * c2 - a2 * c1) / slopeDiff;
        answer = {x, y};
    }
    
    return answer;
}

Python (3.5)

'''
    Time Complexity : O(1)
    Space Complexity : O(1)
'''

def findIntersection(ax1, ay1, bx1, by1, px2, py2, qx2, qy2):
    answer = []
    # Line AB will be represented as a1x + b1y = c1.
    a1 = by1 - ay1
    b1 = ax1 - bx1
    c1 = a1 * ax1 + b1 * ay1

    # Line CD will be represented as a2x + b2y = c2.
    a2 = qy2 - py2
    b2 = px2 - qx2
    c2 = a2 * px2 + b2 * py2

    slopeDiff = a1 * b2 - a2 * b1

    if (slopeDiff == 0):
        answer = [-1, -1]
    else:
        x = (b2 * c1 - b1 * c2) / slopeDiff
        y = (a1 * c2 - a2 * c1) / slopeDiff
        answer = [x, y]
    
    return answer

Note:

For Example: For A(0, 3), B(3, 0) and P(0, 0), Q(5, 5) the point of intersection of line ‘AB’ and ‘PQ’ is (1.500000, 1.500000). As shown below:

As Ninja is weak in Geometry, can you help him to find the intersection of these two lines?

Input Format

Output Format :

Note:

Constraints:

Top Atlassian Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Atlassian Software Developer Intern