PROBLEM LINK:
Author: Kanstantsin Sokal
Tester: Pavel Sheftelevich
Editorialist: Pawel Kacprzak
DIFFICULTY:
Cakewalk
PREREQUISITES:
Basic geometry
PROBLEM:
For a given triangle, you have to classify it according to its sides and angles.
QUICK EXPLANATION:
Use Euclidean distance to classify triangles according to their sides. You can use Pythagorean theorem in order to classify them according to their angles.
EXPLANATION:
In this problem, your task is to classify a triangle given as 3 point with integer coordinates. It’s important to notice that there are no degenerated triangles in the input - this ones with all 3 collinear points.
Since all coordinates are integers, we are going to give a solution, which uses only operations over integers in order to avoid any floating point equality checking. This is a common trick, and it’s worth to consider using it while solving this kind of problems.
SUBTASK 1
In the first subtask, you have to classify a triangle based on the lengths of the its sides, and there are two options here: either a triangle has exactly 2 sides of equal lengths or all its sides have different lengths. A triangle with all sides of equal lengths is guaranteed to not appear in the test cases, so we don’t consider such a triangles here.
The task is supposed to be pretty straightforward. Let d^2(A, B) be the squared distance between points A and B. In other words, this is the squared length of a side of the triangle between points A and B.
Notice that d^2(A, B) can be easily computed (A.x - B.x)^2 + (A.y - B.y)^2, because its just a squared Euclidean distance.
In order to classify a triangle according to its sides, the only thing we need to do is to compare squared lengths of all its 3 sides. Either none of them are equal or exactly 2 of them are equal, which gives us the answer. Notice that we are using the fact that for two positive integers C and D, C and D are equal if and only if C^2 and D^2 are equal. This let us to avoid floating point operations here.
SUBTASK 2
In the second subtask, besides doing the side classification as in the first subtask, you have to classify triangles according to their angles. More specifically, there are 3 options here. A given triangle may have either one right angle or one obtuse angle or all acute angles.
This seems to be slightly harder than the first subtask. You may think of using some sort of trigonometry functions here, but in fact, there is a quite clever and smooth solution based on Pythagorean theorem.
Let a^2, b^2, c^2 be the squared lengths of sides of a triangle in non-descending order. Then the triangle has exactly one right angle if and only if a^2 + b^2 = c^2. Moreover, it has exactly one obtuse angle if and only if a^2 + b^2 < c^2. Otherwise, all its angles are acute. Since we know how to compute squared lengths of all the sides, we can easily classify a triangle according to its angles using this method. Notice that all these computations are again done only over integers.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
