Last Updated: 18 Apr, 2021
NINJA’S AFFAIR
Moderate
Asked in company
Ninja started using a dating app and he got two matches. Now Ninja becomes greedy and thinks of dating both of them at the same time. So he wants to check the number of the affair points from which the distance between Ninja and both the matches becomes equal.
Given a 2D array/list DISTANCE[i] = [Xi, Yi] of size 'N' x 2, an affair point is defined as a tuple of points ( I, J, K ) such that distance between ‘I’ and ‘J’ equals the distance between ‘I’ and ‘K’.
As Ninja is busy getting ready for his date, he asks you for help. So your task is to find the numbers of affair points.
Note:
1. The distance between two points (X1, Y1) and (X2, Y2) is calculated as [ (X1 - X2) ^ 2 + (Y1 - Y2) ^ 2 ] i.e without a square root.
2. The order of tuples matters.
Example:
Suppose the given 'DISTANCE' array/list is [ [ 0, 0 ], [ 1, 0 ], [ 2, 0 ] ]. We return ‘2’as the answer as only two affair points are there as follows:
[ [ 1, 0 ], [ 0, 0 ], [ 2, 0 ] as ( ( 0 - 1) * ( 0 - 1 ) + (0 - 0 ) * ( 0 - 0 ) = ( 2 - 1 ) * ( 2 - 1 ) + ( 0 - 0 ) * ( 0 - 0 ) = 1
Distance of [1, 0] is same for [0, 0] and [2, 0].
[ [ 1, 0 ], [ 2, 0 ], [ 0, 0 ] ] as ( ( 2 - 1 ) * ( 2 - 1 ) + ( 0 - 0 ) * ( 0 - 0 ) = ( 0- 1 ) * ( 0 - 1 ) + ( 0 - 0 ) * ( 0 - 0 )
Distance of [1, 0] is same for [2, 0] and [0, 0].
Input Format:
The first line of input contains the ‘T’ number of test cases.
The first line of each test case contains an integer ‘N’ denoting the number of points in the ‘DISTANCE’ list/array. Then, ‘N’ lines follow.
Each line contains two space-separated integers denoting the points ‘Xi, Yi’.
Output Format:
For each test case, print a single line containing a single integer denoting the total number of possible affair points.
The output of each test case will be printed in a separate line.
Note:
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 50
1 <= ‘N’ <= 100
-10000 <= ‘DISTANCE[i][0]’, 'DISTANCE[i][1] <= 10000
Where ‘T’ represents the number of test cases, ‘N’ represents the size of the ‘DISTANCE’ array/list, and 'DISTANCE[i][0]' represents the point 'Xi' and 'DISTANCE[i][1]' represents the point 'Yi'.
Time Limit: 1 sec.
Approaches
The idea here is to use the brute force approach and check for each and every possible pair. If there is any pair of points satisfying the given condition of being an affair point, we increase the count by ‘1’.
- First, we declare a variable named ‘COUNT = 0’ and initialize it with ‘0’.
- Run a loop where ‘i’ ranges from ‘0’ to ‘N’.
- Run another loop where ‘j’ ranges from ‘0’ to ‘N’.
- If ‘j’ == ‘i’ continue the loop.
- Else run another loop where ‘k’ ranges from ‘0’ to ‘N’
- If ‘k’ == ‘j’ continue the loop.
- Compare the distance of point ‘i’ to ‘j’ and ‘i’ to ‘k’.
- If the distance is equal, increase ‘COUNT’ by ‘1’.
- Run another loop where ‘j’ ranges from ‘0’ to ‘N’.
- Return the ‘COUNT’.
The idea here is to store the distances in the map. Now if the same distance comes, we can count how many times the same distance has already occurred and we can increase the count by that number of occurrences without the need for checking with each pair. Thus, the time complexity can be reduced.
- First, we declare a variable named ‘COUNT’ and initialize it with ‘0’ and an unordered map ‘MAP’.
- Run a loop where ‘i’ ranges from ‘0’ to ‘N’
- Run a loop where ‘j’ ranges from ‘0’ to ‘N’
- If ‘i’ == ‘j’ continue the loop.
- Now we calculate the distance between the two points and check if this distance exists in ‘MAP’.
- If it doesn’t exist, we simply insert it into ‘MAP’.
- Else we check how many times this distance is present on the map and increase the ‘COUNT’ by ‘2’ times the number of times that distance is present in the map.
- Run a loop where ‘j’ ranges from ‘0’ to ‘N’
- After the iteration, we return ‘COUNT’ as the output.