You are not logged in. Please login at www.codechef.com to post your questions!

×

RIGHTTRI - Editorial

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Pushkar Mishra

DIFFICULTY:

Easy

PREREQUISITES:

Binary search

PROBLEM:

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.

COMPLEXITY:

$\mathcal{O}(\log N)$ per test case.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

This question is marked "community wiki".

asked 18 Jun '16, 16:06

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156281
accept rate: 4%

edited 27 Jun '16, 00:14

admin's gravatar image

0★admin ♦♦
15.9k347484508

cannot access links to solutions.

(27 Jun '16, 00:05) shubhambhattar3★

16

Hey can anyone upvote me. Karma 1 problem :(

link

answered 27 Jun '16, 10:12

easy_'s gravatar image

2★easy_
1286
accept rate: 0%

11

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)

link

answered 27 Jun '16, 00:14

aayushdw's gravatar image

5★aayushdw
813
accept rate: 0%

edited 27 Jun '16, 00:40

Solved in O(1):

Formula: Sin(2A)=4S/(H * H)

Where H is Hypotenuse,S is Area and A is the angle between base and Hypotenuse.

Note: Solution does not exist if 4S > H*H

Proof:

Let 'a' be the Perpendicular and 'b' be the Base.

Area=S=ab/2, Sin(A)=a/H, Cos(A)=b/H

Sin(A)Cos(A)= ab/(H * H)

Therefore Sin(2A)=4S/(H * H) because Sin(2A)=2Sin(A)Cos(A) and S=ab/2

Therefore Sides are HSin(A), HCos(A) ,H

My solution https://www.codechef.com/viewsolution/10622622

link

answered 27 Jun '16, 00:23

ishpreet's gravatar image

4★ishpreet
9916
accept rate: 0%

edited 27 Jun '16, 08:53

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

link

answered 27 Jun '16, 00:10

tihorsharma123's gravatar image

4★tihorsharma123
3027
accept rate: 15%

Why go for binary search if we can go for an O(1) solution ??(Assuming sqrt operation takes constant time)!

link

answered 27 Jun '16, 00:07

sandeep9's gravatar image

3★sandeep9
4782627
accept rate: 4%

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.

Link to my O(1) solution : https://www.codechef.com/viewsolution/10617012

link

answered 27 Jun '16, 00:17

sdssudhu's gravatar image

5★sdssudhu
72429
accept rate: 13%

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.

Refer to this code for more clearity. Code

link
This answer is marked "community wiki".

answered 27 Jun '16, 00:20

lohit_97's gravatar image

4★lohit_97
3108
accept rate: 2%

@tihorsharma123 No you cant. It will overflow in C++.

link

answered 27 Jun '16, 00:21

beginner007's gravatar image

2★beginner007
11
accept rate: 0%

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

(27 Jun '16, 00:33) tihorsharma1234★

link to O(1) Solution in python https://www.codechef.com/viewsolution/10624650

link

answered 27 Jun '16, 00:25

swetankmodi's gravatar image

6★swetankmodi
3535
accept rate: 22%

hey,can anyone tell me the error in code. https://www.codechef.com/viewsolution/10623374

link

answered 27 Jun '16, 00:59

nanhe's gravatar image

3★nanhe
413
accept rate: 0%

@nanhe , I think the formula you are using is wrong. Correct formula is

$a=\sqrt{\frac{H^2+\sqrt{H^4-16S^2}}{2}}$ and $b=\sqrt{\frac{H^2-\sqrt{H^4-16S^2}}{2}}$

and ofcourse thing inside squareroot has to be positive or non-negative.

link

answered 27 Jun '16, 01:55

prakhariitd's gravatar image

6★prakhariitd
1.1k19
accept rate: 10%

edited 27 Jun '16, 02:00

@prakhariitd

how i have derived the formula is

(h^2)=(a^2)+(b^2)

(h^2)+(2ab)=a^2+(b^2)+(2ab) (we know s=(ab)/2 therefore (2s)=(a*b))

(h^2)+(4*s)=(a+b)^2

a+b=sqrt((h^2)+(4*s)) -------------(1)

and b=(2*s)/a; ------------(2)

substituting the value of b in equation 1 and assume sqrt((h^2)+(4*s)) as z

therefore,equation becomes

(a^2)-(a*z)+2s=0

and a=(z+(sqrt((zz)-(8s))))/2;

and b can be calculated using equation 2

so,whats wrong in this....

link

answered 27 Jun '16, 02:16

nanhe's gravatar image

3★nanhe
413
accept rate: 0%

Please help, getting WA..

#include <stdio.h>
#include <math.h>

int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--){
        long long h, s;
        scanf("%lld %lld", &h, &s);
        if(h * h <= 4 * s) {
            printf("-1\n");
            continue;
        }
        double a = fabs(sqrt(h * h + 4 * s));
        double b = fabs(sqrt(h * h - 4 * s));
        printf("%lf %lf %lf\n", (a - b)/2, (a + b)/2, (double) h);
    }
    return 0;
}
link

answered 27 Jun '16, 16:41

pragyan_123's gravatar image

2★pragyan_123
11
accept rate: 0%

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 : https://www.codechef.com/viewsolution/10627917

link

answered 27 Jun '16, 16:43

inishona_29's gravatar image

2★inishona_29
11
accept rate: 0%

edited 27 Jun '16, 16:46

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,590
×2,610
×594
×42
×3

question asked: 18 Jun '16, 16:06

question was seen: 3,857 times

last updated: 27 Jun '16, 16:46