Distinct Scalene Triangles
National Olympiad — Municipal round (2019 season)
Submission name: triplets.cpp
Problem summary
Given segment lengths, count distinct scalene triangles that can be formed. Triangles with the same three side lengths count once, regardless of which segment copies are chosen.
Input
n, then n segment lengths.
Output
The number of distinct valid triangles.
Constraints
3 ≤ n ≤ 199; 1 ≤ a[i] ≤ 199.
Worked example
An independently prepared example for this explanation.
Input
5 9 2 9 8 4
Output
2
Solution analysis
- A scalene triangle uses three different lengths, so multiplicities of input segments are irrelevant. Sort the lengths and remove duplicates.
- Enumerate indices i<j<k in the distinct sorted array. The only triangle inequality that needs testing is a[i]+a[j]>a[k], because the other two follow from positivity and sorted order.
- The example reduces to 2,4,8,9. The valid triples are (2,8,9) and (4,8,9). The two copies of 9 do not create any additional triangle.
Why it works
Every scalene triangle corresponds to one unique increasing triple of distinct available lengths. Enumeration visits that triple once. For increasing positive lengths the largest side is the only side that can fail the triangle inequality, so the test accepts exactly realizable triangles.
Watch out. Do not count choices of identical segment copies. Equality in the triangle inequality gives a degenerate triangle and must be rejected.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
// Algorithm: A scalene triangle uses three different lengths, so multiplicities of input
// segments are irrelevant.
using namespace std;
int main(){
int n;
cin>>n;
vector<int>length(n);
for(int&value:length){
cin>>value;
}
sort(length.begin(),length.end());
length.erase(unique(length.begin(),length.end()),length.end());
int answer=0;
int distinct=static_cast<int>(length.size());
for(int i=0;i<distinct;i++){
for(int j=i+1;j<distinct;j++){
for(int k=j+1;k<distinct;k++){
answer+=length[i]+length[j]>length[k];
}
}
}
cout<<answer<<'\n';
}