Module: Ternary search


Problem

8 /9


Nested ternary search: soccer goals

Theory Click to read/hide

Nested ternary search can be applied when we have an optimization problem with two unknowns. This task is just about that.

Obviously, the gate will be in the shape of a quadrilateral, with a right angle at the base, then we just have to choose 2 corners (α and β) so that the area gate was maximum. To do this, we create a ternary search that will give us 2 corners (α1and α2), and for each of these α we will run another ternary search, which will select such β for which the area will be maximum.

Read more here

Problem

Sonya, unlike many students of math-mech, is athletic not only in programming. One day she went to play football with her friends. Unfortunately, there was no specially equipped football field anywhere nearby, only a tall birch stood alone in the back of the yard. After rummaging around in the pantry at home, Sonya found two sticks and decided to build a football goal out of sticks and birch. Of course, birch will be used as one of the side posts. It remains to make a second rack and a crossbar out of two sticks.
Sonya, of course, wants to score as many goals as possible. Therefore, she decided to make the gate of the maximum area. Standard football goals are rectangular, but Sonya — a creative person, and she believes that the gate can be in the form of an arbitrary quadrangle.

We can assume that birch is a straight line segment and grows strictly perpendicular to the ground.
 
Input
A single line contains the integers a, b  — stick lengths (\(1 <= a, b <= 10 000\)). It is known that the total length of the sticks is strictly less than the height of the birch.

Output
Print the maximum area of ​​a gate that can be built from sticks and birch. The answer should be displayed with an accuracy of at least six decimal places.

 

Examples
# Input Output
1 2 2 4.828427125 
Source: Ural Regional Team Programming Olympiad 2011

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!