Given N points in a plane in the form of 2D array such that every row consist of two integer L and R where L belongs to x-ordinate and R belongs to y-ordinate. The task is to count the triplets of points(say a, b & c) such that distance between a & b is equals to the distance between a & c.
Note: The order of triplets matters.
Examples:
Input: arr[] = { { 0, 0 }, { 1, 0 }, { 2, 0 } }
Output: 2
Explanation:
The possible triplets are: {{1, 0}, {0, 0}, {2, 0}} and {{1, 0}, {2, 0}, {0, 0}}Input: arr[] = { {1, 0}, {1, -1}, {2, 3}, {4, 3}, {4, 4} }
Output: 0
Explanation:
There is no such triplets exists.
Approach:
- For each point calculate it’s distance to every other points.
- Store intermediate distances(say d) for point to other points in a Map.
- If Map has already same distance then count of triplets is twice the value stored for d in Map.
- Update the count of current distance in the Map.
Below is the implementation of the above:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the triplets int countTriplets(vector<vector< int > >& p) { // Initialise count int count = 0; // Traverse the arr[] for ( int i = 0; i < p.size(); i++) { // Map to store the distance between // every pairs p[i] and p[j] unordered_map< int , int > d; for ( int j = 0; j < p.size(); j++) { // Find the distance int dist = pow (p[j][1] - p[i][1], 2) + pow (p[j][0] - p[i][0], 2); // If count of distance is greater // than 0, then find the count if (d[dist] > 0) { count += 2 * d[dist]; } // Update the current count of the // distance d[dist]++; } } // Return the count of triplets return count; } // Driver Code int main() { // Set of points in plane vector<vector< int > > arr = { { 0, 0 }, { 1, 0 }, { 2, 0 } }; // Function call cout << countTriplets(arr); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to count the triplets static int countTriplets( int p[][]) { // Initialise count int count = 0 ; // Traverse the arr[] for ( int i = 0 ; i < p.length; i++) { // Map to store the distance between // every pairs p[i] and p[j] HashMap<Integer, Integer> d = new HashMap<Integer,Integer>(); for ( int j = 0 ; j < p.length; j++) { // Find the distance int dist = ( int )(Math.pow(p[j][ 1 ] - p[i][ 1 ], 2 )+ Math.pow(p[j][ 0 ] - p[i][ 0 ], 2 )); // If count of distance is greater // than 0, then find the count if (d.containsKey(dist) && d.get(dist) > 0 ) { count += 2 * d.get(dist); } // Update the current count of the // distance if (d.containsKey(dist)){ d.put(dist,d.get(dist)+ 1 ); } else d.put(dist, 1 ); } } // Return the count of triplets return count; } // Driver Code public static void main(String args[]) { // Set of points in plane int arr[][] = { { 0 , 0 }, { 1 , 0 }, { 2 , 0 } }; // Function call System.out.println(countTriplets(arr)); } } // This code is contributed by AbhiThakur |
Python3
# Python3 program for the above approach # Function to count the triplets def countTriplets(p) : # Initialise count count = 0 ; # Traverse the arr[] for i in range ( len (p)) : # Map to store the distance between # every pairs p[i] and p[j] d = {}; for j in range ( len (p)) : # Find the distance dist = pow (p[j][ 1 ] - p[i][ 1 ], 2 ) + \ pow (p[j][ 0 ] - p[i][ 0 ], 2 ); if dist not in d : d[dist] = 0 ; # If count of distance is greater # than 0, then find the count if (d[dist] > 0 ) : count + = 2 * d[dist]; # Update the current count of the # distance d[dist] + = 1 ; # Return the count of triplets return count; # Driver Code if __name__ = = "__main__" : # Set of points in plane arr = [ [ 0 , 0 ], [ 1 , 0 ], [ 2 , 0 ] ]; # Function call print (countTriplets(arr)); # This code is contributed by Yash_R |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to count the triplets static int countTriplets( int [,] p) { // Initialise count int count = 0; // Traverse the arr[] for ( int i = 0; i < p.GetLength(0); i++) { // Map to store the distance between // every pairs p[i] and p[j] Dictionary< int , int > d = new Dictionary< int , int >(); for ( int j = 0; j < p.GetLength(0); j++) { // Find the distance int dist = ( int )(Math.Pow(p[j, 1] - p[i, 1], 2) + Math.Pow(p[j, 0] - p[i, 0], 2)); // If count of distance is greater // than 0, then find the count if (d.ContainsKey(dist) && d[dist] > 0) { count += 2 * d[dist]; } // Update the current count of the // distance if (d.ContainsKey(dist)) { d[dist]++; } else d.Add(dist, 1); } } // Return the count of triplets return count; } // Driver code static void Main() { // Set of points in plane int [,] arr = new int [3, 2]{ { 0, 0 }, { 1, 0 }, { 2, 0 } }; // Function call Console.WriteLine(countTriplets(arr)); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript program for the above approach // Function to count the triplets function countTriplets(p) { // Let initialise count let count = 0; // Traverse the arr[] for (let i = 0; i < p.length; i++) { // Map to store the distance between // every pairs p[i] and p[j] let d = new Map(); for (let j = 0; j < p.length; j++) { // Find the distance let dist = (Math.pow(p[j][1] - p[i][1], 2)+ Math.pow(p[j][0] - p[i][0], 2)); // If count of distance is greater // than 0, then find the count if (d.has(dist) && d.get(dist) > 0) { count += 2 * d.get(dist); } // Update the current count of the // distance if (d.has(dist)){ d.set(dist,d.get(dist)+1); } else d.set(dist,1); } } // Return the count of triplets return count; } // Driver code // Set of points in plane let arr = [[ 0, 0 ], [ 1, 0 ], [ 2, 0 ]]; // Function call document.write(countTriplets(arr)); </script> |
2
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!