Given two numbers H and S, find a right triangle such that the hypotenuse is of length H and its area is S. If no such triangle exists, output -1.
EXPLANATION:
A right triangle with a fixed hypotenuse H has a very nice property related to areas: the maximum area will be when the triangle is isosceles, i.e., base B and perpendicular P are equal. This implies that the maximum area will be when B=P=\sqrt{\frac{H^2}{2}} (follows from the pythagorus theorem P^2 + B^2 = H^2).
Let us only talk in terms of the base B. So, when B = \sqrt{\frac{H^2}{2}}, then the area is maximised. For all other bases from 0 up to this limit, the area monotonically increases. Also, beyond this limit, area monotonically decreases.
That is the main hint: MONOTONICITY! We can binary search on the base B between the limits 0 and \sqrt{\frac{H^2}{2}} because beyond this value, the behavior is symmetric. By binary searching on the base, we mean that we try bases such that we can reach our target area.
While binary searching, we have to take care of the fact that we remain in the error bound. Since we want the error in our answers to be less than 0.01, it would be best that we do a binary search such that the area of the resultant triangle with the given base has error less than 10^{-8} when compared with given area S. This is because only then, the absolute error in side will be less than 0.01 (this follows from the fact that we are using square root to calculate the other side and also that area is the product of the sides).
Please see editorialist’s/setter’s program for implementing binary search with that precision.
We can also solve by quadratic equation : let a and b the other two side lengths. then a^2 + b^2 =h and ab=2*s
we can get a quadratic equation in a we can be solved by root formula subsequently check whether the roots are possible or not
The can be solved in O(1). Let’s denote base by b and perpendicular by p. Now we have two equations b*p/2=s , b^2+p^2=h^2 This can be written as b^2+p^2+2bp = (b+p)^2 = h^2+4s and b^2+p^2-2bp = (b-p)^2 = h^2-4s. It can be seen that for solution to exist h^2-4s>=0. If the above condition is satisfied then b=(x+y)/2 and p=(x-y)/2
where, x=sqrt(h^2+4s) and y=sqrt(h^2-4s). Now print the answer as p,b,h (non-decreasing order)
There is a O(1) solution as follows : h^2=a^2+b^2 and 2 * area=a * b . So you can find a+b and a-b using (a+b)^2 and (a-b)^2 and from it a and b . If a and b are positive then the solution exists.
Well, I did not use Binary Search. My solution is O(1) or say O(logH), if, computing square root is considered as O(logH).
Let sides be A and B. H be the hypotenuse and S be the area.
So, a^2 + b^2 = h^2 and ab = 2S.
Solving these two equations, we directly get A and B. So, you will notice that real values for A and B exist only if h^2 - 4S >= 0, and that is our condition to check possibility of a solution or not.
We can do this in O(1)
let x be the base and y be the height of right triangle.
Then,
x^2+y^2=H^2 …(1)
and xy=2S…(2)
From these two equations , we get
x^4 -(Hx)^2+ 4*S^2=0
NoW let x^2=t
then we have the equation t^2-H^2t+4S^2=0
Discriminate D = H^4-16S^2
IF D<0 , solution does not exist
else
t=x^2 = (H^2 + sqrt(D) ) / 2 so x= sqrt( (H^2 + sqrt(D) ) / 2 )
and from eq 2. y = 2S/x;
Link to C++ Code : CodeChef: Practical coding for everyone
Can someone please explain how error bound is being calculated here (10^-8 here)???
And what other cases might appear for calculating error bounds for such problems and how to calculate error bound for those cases too??
U will get discriminant as h^4- 16s^2 ryt?
write it as (h^2)^2-(4s)^2 then this (h^2-4s)(h^2+4*s) now it wont overflow hope u got it if you have any doubts you can ask me
@pushkarmishra, in solutions provided, you do binary search with tolerence=1e-12,when start is close to end, it would take a lot of steps to have a significant change. How do you guarentee it to not give a TLE (i.e. How do you find its time complexity )?