Counting Triangles
Given a list of N triangles with integer side lengths, determine how many different triangles there are. Two triangles are considered to be the same if they can both be placed on the plane such that their vertices occupy exactly the same three points.
Signature
int countDistinctTriangles(ArrayList arr)
or
int countDistinctTrianges(int[][] arr)
Input
In some languages, arr is an Nx3 array where arr[i] is a length-3 array that contains the side lengths of the ith triangle. In other languages, arr is a list of structs/objects that each represent a single triangle with side lengths a, b, and c.
It's guaranteed that all triplets of side lengths represent real triangles.
All side lengths are in the range [1, 1,000,000,000]
1 <= N <= 1,000,000
Output
Return the number of distinct triangles in the list.
Example 1
arr = [[2, 2, 3], [3, 2, 2], [2, 5, 6]]
output = 2
The first two triangles are the same, so there are only 2 distinct triangles.
Example 2
arr = [[8, 4, 6], [100, 101, 102], [84, 93, 173]]
output = 3
All of these triangles are distinct.
Example 3
arr = [[5, 8, 9], [5, 9, 8], [9, 5, 8], [9, 8, 5], [8, 9, 5], [8, 5, 9]]
output = 1
All of these triangles are the same.
I could do it with below logic. but it feels like it is sub-optimal. Is there a better way to do it?
I thought of finding out distinct triangles using set of sets of side lengths. However, in C++ it doesnt allow to create an unordered_set of unordered_set<>, as there is no internal hash function to create hashes for sets.
Am I thinking right? please suggest.
The logic I used:
int countDistinctTriangles(vector <sides> arr) {
// Write your code here
unordered_set<string> uset;
long long max1=0;
long long max2=0;
string s;
for(auto t:arr)
{
if(t.a>t.b)
{
max1=t.a;
max2=t.b;
}
else
{
max1=t.b;
max2=t.a;
}
if(t.c>max1)
{
s=to_string(t.c)+to_string(max1)+to_string(max2);
}
else if(t.c>max2)
{
s=to_string(max1)+to_string(t.c)+to_string(max2);
}
else
{
s=to_string(max1)+to_string(max2)+to_string(t.c);
}
uset.insert(s);
}
return uset.size();
}