Given an array arr containing N points, the task is to find the total number of triplets in which the points are equidistant.
A triplet of points (P1, P2, P3) is said to be equidistant when the distance between P1 and P2 is the same as of the distance between P1 and P3.
Note: The order of the points matters, i.e., (P1, P2, P3) is different from (P2, P3, P1).
Example:
Input: arr = [[0, 0], [1, 0], [2, 0]]
Output: 2
Explanation:
Since the order of the points matters, we have two different sets of points [[1, 0], [0, 0], [2, 0]] and [[1, 0], [2, 0], [0, 0]] in which the points are equidistant.Input: arr = [[1, 1], [1, 3], [2, 0]]
Output: 0
Explanation:
It is not possible to get any such triplet in which the points are equidistant.
Approach: To solve the problem mentioned above, we know that the order of a triplet matter, so there could be more than one permutations of the same triplet satisfying the condition for an equidistant pair of points.
- First, we will compute all the permutations of a triplet which has equidistant points in it.
- Repeat this same process for every different triplet of points in the list. To calculate the distance we will use the square of the distance between the respective coordinates.
- Use hashmap to store the various number of equidistant pairs of points for a single triplet.
- As soon as we count the total number of pairs, we calculate the required permutation. We repeat this process for all different triplets and add all the permutations to our result.
Below is the implementation to the above approach:
C++
// C++ implementation to Find// the total number of Triplets// in which the points are Equidistant#include <bits/stdc++.h>using namespace std;// function to count such tripletsint numTrip(vector<pair<int, int> >& points){ int res = 0; // Iterate over all the points for (int i = 0; i < points.size(); ++i) { unordered_map<long, int> map(points.size()); // Iterate over all points other // than the current point for (int j = 0; j < points.size(); ++j) { if (j == i) continue; int dy = points[i].second - points[j].second; int dx = points[i].first - points[j].first; // Compute squared euclidean distance // for the current point int key = dy * dy; key += dx * dx; map[key]++; } for (auto& p : map) // Compute nP2 that is n * (n - 1) res += p.second * (p.second - 1); } // Return the final result return res;}// Driver codeint main(){ vector<pair<int, int> > mat = { { 0, 0 }, { 1, 0 }, { 2, 0 } }; cout << numTrip(mat); return 0;} |
Java
// Java implementation to find the total // number of Triplets in which the // points are Equidistantimport java.util.*;@SuppressWarnings("unchecked")class GFG{ static class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; }} // Function to size() such tripletsstatic int numTrip(ArrayList points){ int res = 0; // Iterate over all the points for(int i = 0; i < points.size(); ++i) { HashMap<Long, Integer> map = new HashMap<>(); // Iterate over all points other // than the current point for(int j = 0; j < points.size(); ++j) { if (j == i) continue; int dy = ((pair)points.get(i)).second - ((pair)points.get(j)).second; int dx = ((pair)points.get(i)).first - ((pair)points.get(j)).first; // Compute squared euclidean distance // for the current point long key = dy * dy; key += dx * dx; if (map.containsKey(key)) { map.put(key, map.get(key) + 1); } else { map.put(key, 1); } } for(int p : map.values()) // Compute nP2 that is n * (n - 1) res += p * (p - 1); } // Return the final result return res;} // Driver codepublic static void main(String []args){ ArrayList mat = new ArrayList(); mat.add(new pair(0, 0)); mat.add(new pair(1, 0)); mat.add(new pair(2, 0)); System.out.println(numTrip(mat));}}// This code is contributed by rutvik_56 |
Python3
# Python3 implementation to find# the total number of Triplets# in which the points are Equidistant # Function to count such tripletsdef numTrip(points): res = 0 # Iterate over all the points for i in range(len(points)): map = {} # Iterate over all points other # than the current point for j in range(len(points)): if (j == i): continue dy = points[i][1] - points[j][1] dx = points[i][0] - points[j][0] # Compute squared euclidean distance # for the current point key = dy * dy key += dx * dx map[key] = map.get(key, 0) + 1 for p in map: # Compute nP2 that is n * (n - 1) res += map[p] * (map[p] - 1) # Return the final result return res # Driver codeif __name__ == '__main__': mat = [ [ 0, 0 ], [ 1, 0 ], [ 2, 0 ] ] print (numTrip(mat)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation to find the total // number of Triplets in which the // points are Equidistantusing System;using System.Collections;using System.Collections.Generic;class GFG{class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; }} // Function to count such tripletsstatic int numTrip(ArrayList points){ int res = 0; // Iterate over all the points for(int i = 0; i < points.Count; ++i) { Dictionary<long, int> map = new Dictionary<long, int>(); // Iterate over all points other // than the current point for(int j = 0; j < points.Count; ++j) { if (j == i) continue; int dy = ((pair)points[i]).second - ((pair)points[j]).second; int dx = ((pair)points[i]).first - ((pair)points[j]).first; // Compute squared euclidean distance // for the current point int key = dy * dy; key += dx * dx; if (map.ContainsKey(key)) { map[key]++; } else { map[key] = 1; } } foreach(int p in map.Values) // Compute nP2 that is n * (n - 1) res += p * (p - 1); } // Return the final result return res;} // Driver codepublic static void Main(string []args){ ArrayList mat = new ArrayList(){ new pair(0, 0), new pair(1, 0), new pair(2, 0) }; Console.Write(numTrip(mat));}}// This code is contributed by pratham76 |
Javascript
<script>// Javascript implementation to find the total// number of Triplets in which the points are// Equidistant// Function to size() such tripletsfunction numTrip(points){ let res = 0; // Iterate over all the points for(let i = 0; i < points.length; ++i) { let map = new Map(); // Iterate over all points other // than the current point for(let j = 0; j < points.length; ++j) { if (j == i) continue; let dy = points[i][1] - points[j][1]; let dx = points[i][0] - points[j][0]; // Compute squared euclidean distance // for the current point let key = dy * dy; key += dx * dx; if (map.has(key)) { map.set(key, map.get(key) + 1); } else { map.set(key, 1); } } for(let [key, value] of map.entries()) // Compute nP2 that is n * (n - 1) res += value * (value - 1); } // Return the final result return res;}// Driver codelet mat = [];mat.push([0, 0]);mat.push([1, 0]);mat.push([2, 0]);document.write(numTrip(mat));// This code is contributed by unknown2108</script> |
Output:
2
Time Complexity: O(N2)
Auxiliary Space: O(N)
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!
