Superheronian Triangles
National Olympiad — Municipal round (2019 season)
Submission name: superheron.cpp
Problem summary
Count noncongruent triangles of perimeter P whose side lengths, area, inradius, and circumradius are all positive integers.
Input
One positive perimeter P.
Output
The number of eligible triangles.
Constraints
1 ≤ P ≤ 50,000.
Worked example
Official sample, transcribed with whitespace restored from the PDF.
Input
240
Output
4
Solution analysis
- An integer-area triangle with integer sides has even perimeter: Heron’s identity 16S²=P(P−2a)(P−2b)(P−2c) would have an odd right side if P were odd. Return zero in that case. Otherwise put s=P/2 and x=s−a, y=s−b, z=s−c. The triangle inequalities are equivalent to positive x,y,z with x+y+z=s.
- Enumerate 1≤x≤y≤z by taking x≤s/3 and x≤y≤(s−x)/2, then z=s−x−y. This lists each side multiset once. Since S²=sxyz and r=S/s, an integral inradius requires xyz/s to be an integer square. First test divisibility, then take an integer-corrected square root. If r is integral, S=s·r is integral automatically.
- Finally reconstruct sides s−x,s−y,s−z. The circumradius is abc/(4S), so test that division for zero remainder. For P=240 the four accepted side triples, in increasing order, are (50,78,112), (60,80,100), (40,96,104), and (48,90,102), matching the sample count four.
Why it works
The substitution is a bijection between integer triangles of even perimeter and positive triples summing to s; ordering the triples removes exactly the side permutations. Heron’s formula proves r²=xyz/s, so the divisibility and exact-square tests are equivalent to integral positive r and imply integral area. The final exact divisibility test is equivalent to integral R. Consequently every accepted triple is eligible and every eligible noncongruent triangle is counted exactly once.
Watch out. Do not trust floating-point equality for square roots: correct the estimate with integer comparisons. Reject degenerate triangles by requiring x,y,z>0. Area alone does not ensure integer radii.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The substitution is a bijection between integer triangles of even perimeter and positive
// triples summing to s; ordering the triples removes exactly the side permutations. Heron’s formula
// proves r²=xyz/s, so the divisibility and exact-square tests are equivalent to integral positive r
// and imply integral area.
#include<iostream>
#include<cmath>
using namespace std;
long long integerRoot(long long value){
long long root=static_cast<long long>(sqrt(static_cast<long double>(value)));
while((root+1)*(root+1)<=value){
++root;
}
while(root*root>value){
--root;
}
return root;
}
int main(){
int perimeter;
cin>>perimeter;
if(perimeter%2){
cout<<0<<'\n';
return 0;
}
long long s=perimeter/2;
long long answer=0;
for(long long x=1;3*x<=s;++x){
for(long long y=x;2*y<=s-x;++y){
long long z=s-x-y;
long long product=x*y*z;
if(product%s){
continue;
}
long long radiusSquared=product/s;
long long radius=integerRoot(radiusSquared);
if(radius*radius!=radiusSquared){
continue;
}
long long area=s*radius;
long long sidesProduct=(s-x)*(s-y)*(s-z);
if(sidesProduct%(4*area)==0){
++answer;
}
}
}
cout<<answer<<'\n';
}