PROBLEM LINK:
Author: Misha Chorniy
Tester: Sergey Kulik
Editorialist: Pawel Kacprzak
DIFFICULTY:
EASY
PREREQUISITES:
basic math and geometry
PROBLEM:
For a given integer R, print out all triangles with integer length sides, which has the radius of their inscribed circle equal to R.
QUICK EXPLANATION:
For easier subtasks use explicit iteration over all possible values of triangle sides. For the original constraints, first use simple calculations to reduce the number iterations and then enumerate all triangles.
EXPLANATION:
Let’s assume that in any valid triangle with sides a, b, c, we have a ≥ b ≥c. In solutions to all subtasks, we use the fact that if P = (a + b + c) / 2, then:
R2 = (P - a) * (P - b) * (P - c) / P
It is a basic property of inscribed circle and one can either remember it from math classes or google it.
Subtask 1
In the first subtask, we have R ≤ 3, so one can try to solve the problem by guessing upper bound on a, b, c, iterating over all combinations of them and printing out triangles with sides fulfilling the radius equation. It turns out that for R ≤ 3, the largest side of a valid triangle is 109 for R = 3, so it is possible to iterate over all a, b, c ≤ 200, where 200 can be a random (or not) guess and get accepted for such low constraints.
Subtasks 2 and 3.
For subtasks 2 and 3 more clever methods should be used. Let’s use some math then. The below solution is targeted for the original constraint, however, by missing some of the below analysis, one can came up with a solution passing only constraints in the first and second subtasks.
Just to recall, we have:
a ≥ b ≥ c
P = (a + b + c) / 2
Idea
Let’s define:
X = b + c - a
Y = a + c - b
Z = a + b - c
Then, X + Y + Z = 2 * P.
The idea is to figure out a bound for X as the smallest value among X, Y, Z. This is true, because a is the largest side of a triangle by our assumption.
Bounding X
First, if we take the equation for radius and multiply both sides by P2 , we get:
R2 * P2 = P * (P - a) * (P - b) * (P - c)
Next, observe that:
X = 2 * (P - a)
Y = 2 * (P - b)
Z = 2 * (P - c)
Now, using the fact that X + Y + Z = 2 * P, we can write:
P * X * Y * Z = 8 * P * (P - a) * (P - b) * (P - c) = 8 * R2 * P2 = 4 * R2 * P * (X + Y + P)
After this calculations, we are ready to bound the value of X. Using the fact that X ≤ Y ≤ Z the following holds:
X * X * X / (3 * X) ≤ X * Y * Z / (X + Y + Z) = 4 * R2
The last transition is true because of the above equation P * X * Y * Z = 4 * R2 * P * (X + Y + Z).
Thus, X2 / 3 ≤ 4 * R2, which is equivalent to:
X ≤ 2 * R * sqrt(3)
So in fact X is rather small, which is very nice.
Bounding Y for fixed X
Now, let’s try to define Y, for a fixed X.
Using the analogous method, we can write:
X * Y * Y / (X + Y + Y) ≤ X * Y * Z / (X + Y + Z) = 4 * R2
and from the above equation, it follows that
X * Y * Y - 8 * Y * R2 - 4 * X * R2 ≤ 0,
So for a fixed X, we ca easily iterate over all possible values of Y using the above formula.
Putting it all together
For a fixed X and Y, value of Z can be then computed as:
Z = 4 * R2 * (X + Y) / (X * Y - 4 * R2)
Now, the only remaining thing is to compute values of a, b, c, i.e. the sides of a valid triangle using values of X, Y and Z. For implementation details please refer to setter’s and tester’s solutions.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution will be uploaded soon.
Tester’s solution can be found here.
