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 tripletsint 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 Codeint 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 approachimport 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 tripletsdef 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 Codeif __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 codestatic 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> |
Output:
2
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!