CIVIL - Civil Engineering

no tags 

Civil engineers are people who build impressive structures from concrete and steel. Throughout the world, sky scrapers get ever higher, bridges get ever wider, and tunnels get ever longer. Most recently, the Gotthard Base Tunnel just pushed the limits a bit further...

Gotthard base tunnel

In this task, you take the role of a civil engineer who is to build a tunnel through a mountain. Unfortunately, you have a very limited budget, and must construct the cheapest possible tunnel.

Because engineers have a habit of simplifying things, we will model the mountain and the tunnel using basic geometric shapes. First of all, consider that the earth is flat, and two-dimensional. On this flat surface stands a mountain of height h and width w. Each side of the mountain is parabolic (i.e. satisfies y = ax² + bx + c for some a, b, c). You also know that the base of the mountain is smooth, which means that its steepness at the base is zero.

Graphical view of a tunnel

The tunnel is modeled as a horizontal line through the mountain. The best possible tunnel is the one which minimizes construction cost. This cost is proportional to the length of the road which leads to the tunnel, plus the length of the tunnel itself. Consider that each meter of the tunnel is a factor f times as expensive as a meter of road.


The input file consists of several test cases. Each case is given on a line by itself and consists of the three numbers h, w and f, separated by a space. All these are strictly positive floating point numbers. The input file ends with a test case where all numbers are zero (which must not be processed).


Print for each test case a single number, the optimal height t of the tunnel. Always print three digits after the decimal point. You may assume that it is always cheaper to build some tunnel than to drive over the top of the mountain.


1 2 1.5
9033.66 29752.4 1.56382
0 0 0



hide comments
:D: 2010-11-02 06:44:57

By looking at the submissions, I see that I was the only one with precision issues, but I'll leave an info about them either way.

Of course I was using long double in the entire solution. First I changed math.h methods to long double types. For example "sqrt" to "sqrtl". For some compilers functions like "sqrt" are overloaded for each float type, but it seems that here it uses a standard float type for any argument.

To avoid precision issues when printing, add a very small value (like 0.000001L). This help in cases like in example, when a solution is exactly 0.3125. This is never precisely stored in floating point types. Instead you have 0.3124999..., witch is narrowed down the wrong way.

Last edit: 2010-11-02 06:53:02

Added by:Jonas Wagner
Time limit:0.202s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64