PROBLEM LINK:
Author: Praveen Dhinwa
Testers: Misha Chorniy
Editorialist: Praveen Dhinwa
DIFFICULTY:
easy
PREREQUISITES:
basic geometry, right angle triangles
PROBLEM:
You are given the side lengths of two right angled triangles ABC and DEF.
Length of AB is c, that of AC is b, and that of BC is a. Similarly, the length of DE is f, that of DF is e, and that of EF is d.
The minimum area enclosing axis-parallel rectangle of some figures is defined as a ectangle which is axis parallel (i.e. sides should be parallel to x or y axis) that encloses all the figures and has the minimum possible area.
You have to find a set of coordinates to assign to the points A, B, C, D, E, F such that the minimum area enclosing axis-parallel rectangle of the two triangles has sides L and R (any one side is L and other R). If it is not possible to assign the coordinates, output -1.
SOLUTION
Wlog assume L \le R.
The following conditions should be satisfied in order to a solution to exist
- R \geq max(a, b, c, d)
- L \geq max(min(a, b), \, min(d, e))
Now, we can find a way to construct triangle in this case as follows.
Put C at (0, \, 0) and F at (L, \, R). \Delta ABC will be upwards with C as the bottom left corner of the rectangle. \Delta DEF will be downwards with F as the top right corner of the rectangle.
We can decide the coordinates of A, B, D, E as follows.
If b \geq a, set A = (0, \, b), B = (a, \, 0)
Otherwise, A = (a, \, 0), B = (0, \, b).
If e \geq d, set D = (L, \, R - e), E = (L - d, \, R).
Otherwise, D = (L - e, \, R), E = (L, \, R - d).
