Possible Third Sides of a Triangle
National Olympiad — Municipal round (2019 season)
Submission name: triangle.cpp
Problem summary
Count nonnegative integer c values that form a nondegenerate triangle with positive sides a,b.
Input
a b.
Output
Number of possible c values.
Constraints
1 ≤ a,b < 10^15.
Worked example
Input and output for the worked example discussed below.
Input
3 6
Output
5
Solution analysis
- The three strict triangle inequalities simplify to |a−b|<c<a+b.
- Permitted integers are |a−b|+1 through a+b−1, so their count is a+b−|a−b|−1=2min(a,b)−1.
- For sides 3 and 6, possible third sides are 4,5,6,7,8. The endpoint values 3 and 9 are degenerate and excluded.
Why it works
The strict interval is equivalent to all three triangle inequalities.
Complexity: O(1) time and O(1) space.
Watch out. Use long long and exclude equal endpoints.
Commented C++17 solution
An independently written complete program with standard headers.
// The strict interval is equivalent to all three triangle inequalities.
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
long long a,b;
cin>>a>>b;
cout<<2*min(a,b)-1<<'\n';
}