Ternary search

Plus

Problem description Progress

ID 29484. Nested ternary search: soccer goals

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

ID 29479. house by the road

Темы: Computational geometry Ternary search

The Ministry of Road Transport has decided to build a new office for itself. Since the minister regularly goes out to inspect the most important routes, it was decided that the office of the ministry should not be located too far from them.

The most important alignments are straight lines on the plane. The Ministry wants to choose a location for its office so that the maximum distance from the office to the highways is as short as possible.

You need to write a program that, given the location of the most important highways, determines the optimal location of the house for the office of the Ministry of Road Transport.

Input

The first line of the input file contains a single integer n — number of most important traces (1 ≤ n ≤ 10⁴ ).

The next n lines describe the traces. Each trace is described by four integers x₁, y₁, x₂ and y₂ and is a straight line passing through the points (x₁, y₁) and (x₂, y₂) . The coordinates of the given points do not exceed 10⁴ in absolute value. Dots (x₁ , y₁) and (x₂ , y₂) do not match for any line.

Output

The output file should contain two space-separated real numbers: the coordinates of the point where the office of the Ministry of Road Transport should be built. Modulo coordinates must not exceed 10⁹, it is guaranteed that at least one such answer exists. If there are several optimal answers, print any of them.

The answer must have an absolute or relative error of no more than 10⁻⁶, which means the following. Let the maximum distance from the drawn point to some trace be equal to x, and in the correct answer it is equal to y. The answer will be counted if the value of the expression | x .minus; y | / max(1, |y| ) does not exceed 10⁻⁶.

Input	Output
4 0 0 0 1 0 0 1 0 1 1 2 1 1 1 1 2	0.5000000004656613 0.4999999995343387
7 376 -9811 376 -4207 6930 -3493 6930 -8337 1963 -251 1963 -5008 -1055 9990 -684 9990 3775 -348 3775 1336 7706 -2550 7706 -8412 -9589 8339 -4875 8339	4040.9996151750674 12003.999615175067

Personal Olympiad, All-Russian Olympiad for schoolchildren, Regional stage, 2011, 2nd day, Problem D