ATTENTION!!!
Before posting your query about asking for help make sure that your output for the case
1 3
is
0.2929480435159
PROBLEM LINK:
Author: Anton Lunyov
Tester: Hiroto Sekido
Editorialist: Anton Lunyov
DIFFICULTY:
MEDIUM
PREREQUISITES:
Cylinder volume, Optimization using derivatives
PROBLEM:
You have a rectangle W × H.
You cut it into two rectangles by vertical or horizontal cut.
Then from one of the rectangles you cut out two equal circles of radius R (they can be aligned arbitrarily).
From the second rectangle you cut out the rectangle of the size (2 * π * R) × A for some A.
Moreover, it should be cut parallel to the sides of the second rectangle.
Then you roll up this rectangle to create the lateral surface of the cylinder,
while two circles are used as the top and the bottom of the cylinder respectively.
You goal is to maximize the volume of the cylinder which is π * R * R * A.
Here π ≅ 3.1415926535897932385 is well-known constant.
QUICK EXPLANATION:
Let V(W, H) be the maximum volume of the cylinder provided that the first cut is parallel to the side W.
Clearly, the answer is max(V(W, H), V(H, W)). So we need to calculate V(W, H).
Let our first cut separates two rectangles: W × X and W × (H−X), where 0 < X < H.
We will cut out circles from the first one and the lateral surface from the second one.
We will assume that W is vertical side for simplicity.
Also we denote the diameter of the circle as D.
There are two cases we should consider.
The side H−X is the height of the cylinder.
The optimal value of X in this case is X = min(W/π, 2/3 * H) and the volume is V = π/4 * X * X * (H − X).
The side W is the height of the cylinder.
Then the volume of the cylinder is V = π/4 * D * D * W. So we should maximize D. It can be proved that:
- if H ≥ W * (π + 2) then the maximum value of D is W;
- else if H / (π + 1) ≤ W/2 then the maximum value of D is H / (π + 1);
- else set Hp := H / (π + 1) and Wp := W / (π + 1),
then the maximum value of D is Hp + Wp − sqrt(Wp * (Wp + 2 * Hp − W)).
Also note that your output should have relative error 10-11. Many of you were confused about this.
Let me explain this using example. When W = 100000 and H = 600000 the correct answer is
A = π/4 * 1015 ≅ 785398163397448.309615660845820 rounded to 15 decimal places.
But you don’t need to output such exact value.
Only first 12 digits should be correct (in some cases even 11 digits will be enough).
So output B = 785398163397000.000000000000000 will be considered as correct.
Indeed, |A − B| ≅ 448.309615660845820 while 10-11 * A ≅ 785.398163397448309615660845820.
So we see that |A − B| < 10-11 * A and thus according to the output section such output is correct.
EXPLANATION:
Here we discuss in detail the two cases mentioned in the QUICK EXPLANATION.
The side H−X is the height of the cylinder.
Then π * D ≤ W since we should roll up the second rectangle along the side W.
But then it is clear that circles could be aligned vertically in their rectangle (this is possible once D ≤ W/2).
So the only restriction to cut out the circles is D ≤ X.
It is clear that if D < X then moving the first cut to the left a bit, we will increase the height of the cylinder.
Thus, we can assume that D = X and so X ≤ W/π is the only restriction to construct the cylinder properly.
The volume of the cylinder in this case is V = V(X) = π/4 * X * X * (H − X).
Its derivative at X is V’(X) = π/4 * X * (2 * H − 3 * X).
It has roots 0 and X0 = 2/3 * H.
It is easily seen that V(X) increases at the segment [0, X0] and decreases at [X0, H].
Hence the maximum value of V(X) at the segment [0, W/π] is achieved at the point X = min(W/π, 2/3 * H).
And so this case is completely analyzed:
X = min(W / Pi, 2/3 * H)
V = Pi/4 * X * X * (H - X)
The side W is the height of the cylinder.
Then the volume of the cylinder is V = π/4 * D * D * W.
So we should maximize D.
Horizontally aligned circles.
At first let’s see when it is optimal to cut out horizontally aligned circles.
To cut out the maximal possible circles of diameter W, the side H should be at least W + W + π * W,
so that we can cut out rectangle of size (π * W) × W from the second rectangle.
And it is clear that if H ≥ W * (π + 2) then D = W is maximum possible diameter.
But if H < W * (π + 2) then cutting horizontally aligned circles is not optimal,
since D < W in this case and we can move them a bit and then it will be possible to increase D.
Vertically aligned circles.
Now let’s see when it is optimal to cut out vertically aligned circles.
At first we note, that D ≤ X and π * D ≤ H − X
(because we should roll up the second rectangle along the side H−X to obtain the lateral surface of the cylinder).
Adding these inequalities we get D ≤ H / (π + 1).
To cut out vertically aligned circles, D should be at most W/2.
Assume that W/2 < H / (π + 1).
Then even if we cut out maximum possible vertically aligned circles of diameter W/2,
we will have unused steel after we cut out the lateral surface from the second rectangle.
As in the previous case we could then move circles a bit and this will allow us to increase D.
On the other hand if W/2 ≥ H / (π + 1) then we can cut out two vertically aligned circles of diameter H / (π + 1) (which coincide with one of the upper bound on D) and use the second rectangle as lateral surface without additional cuts.
Thus, we have justified the first to sub-cases mentioned in the QUICK EXPLANATION.
The toughest sub-case.
So now we have W * (π + 1) / 2 < H < W * (π + 2)
and we already know that optimal cutting of circles can’t be vertical or horizontal (in particular D > W/2).
Introduce Cartesian coordinate system and assume that vertexes of the first rectangle have coordinates
(0, 0), (X, 0), (X, W) and (0, W).
Then the optimal way to cut out two circles of radius R = D/2 is to put their centers at points (R, R) and (X − R, W − R).
Moreover, circles should be tangent to each other, otherwise we can decrease X to achieve this.
Hence distance between their centers is D = 2 * R and formula for Euclidean distance yields
(W − D)2 + (X − D)2 = D2.
Since X ≥ D the only proper root is X = X(D) = D + sqrt(W * (2 * D − W))
(recall that D > W/2 so taking sqrt here is correct).
From geometrical reasoning it is clear that X(D) increases as D increases. Hence H − X(D) decreases.
In view of considerations of first two sub-cases in current sub-case we have
H − X(D) > π * D for D = W/2
and
H − X(D) < π * D for D = W.
Hence function f(D) = H − X(D) − π * D is decreasing function having unique zero at [W/2, W].
Clearly this zero is the maximum value of D we are seeking of,
since for every larger value of D we have not enough width to roll up the lateral surface.
So we just need to solve the equation H − X(D) − π * D = 0. It is equivalent to
H − (π + 1) * D = sqrt(W * (2 * D − W))
or
(π + 1)2 * D2 − 2 * (π + 1) * H * D + H2 = 2 * W * D − W2
or
D2 − 2 * (H / (π + 1) + W / (π + 1)2) * D + (H2 + W2) / (π + 1)2 = 0.
Setting Hp := H / (π + 1) and Wp := W / (π + 1)2 we arrive at
D2 − 2 * (Hp + Wp) * D + (Hp2 + W * Wp) = 0.
Discriminant is Wp * (Wp + 2 * Hp − W) and positive in view of condition W * (π + 1) / 2 < H,
which transforms to 2 * Hp > W using our notation.
The general solution of the equation is D = Hp + Wp ± sqrt(Wp * (Wp + 2 * Hp − W)).
But since D should be ≤ Hp then “±” = “−” and we get the formula for D mentioned in the QUICK EXPLANATION.
This finish the solution.
ALTERNATIVE SOLUTION 1:
You may noticed that the author’s solution has a bit different way of calculating the answer 
So here I describe a way how I approached the case when W is the height of the cylinder.
It is quite complicated since I written down restrictions of X and D and never recall the geometric model.
Thus some places are quite technical. I start with the following lemma, partially contained above.
Lemma 1. The maximum D for which we can cut out two non-overlapping circles of diameter D from the rectangle A × B is D = min(A, B, A + B − sqrt(2 * A * B)).
The best way to prove this lemma is to draw a picture since picture is worth a thousand words.
But for me it is easier to write 1000 words than draw a picture 
Introduce Cartesian coordinate system and assume that vertexes of the rectangle has coordinates
(0, 0), (A, 0), (A, B) and (0, B).
The optimal way to cut out two circles of radius R is to put their centers at points (R, R) and (A − R, B − R).
Of course D = 2 * R should not exceed min(A, B).
Since they should not overlap the distance between their centers should be at least 2 * R. Hence
(A − 2 * R)2 + (B − 2 * R)2 ≥ (2 * R)2,
or
(A − D)2 + (B − D)2 ≥ D2,
or
D2 − 2 * (A + B) * D + (A2 + B2) ≥ 0.
Solving this quadratic inequality we get:
either D ≤ A + B − sqrt(2 * A * B) or D ≥ A + B + sqrt(2 * A * B).
But the last case violates condition D ≤ min(A, B).
Hence maximum possible D is min(A, B, A + B − sqrt(2 * A * B)) and we are done.
In the end note that we can’t get rid of A and B in the min since, for example,
when A is much larger than B the number A + B − sqrt(2 * A * B) becomes larger than B.
By Lemma 1 the maximum D for which we can cut out two non-overlapping circles of diameter D from the rectangle W × X is D = min(W, X, W + X − sqrt(2 * W * X)). Hence the complete set of restrictions we have on X and D is the following:
- 0 < X < H.
- 0 ≤ D ≤ min(W, X, W + X − sqrt(2 * W * X)) (because of Lemma 1).
- π * D ≤ H − X (because we should roll up the second rectangle along the side H−X to obtain the lateral surface of the cylinder).
In view of the formula for the volume we should find maximum D for which there exists X,
such that all these inequalities are satisfied.
From D ≤ X and π * D ≤ H − X we have D ≤ H / (π + 1).
Next we should resolve inequality X − sqrt(2 * W) * sqrt(X) + W − D ≥ 0 assuming that X is a variable.
It is equivalent to (X − D)2 ≥ W * (2 * D − W).
If D ≤ W/2, this inequality is satisfied for all X. Thus, analyzing the whole set of restrictions,
we see that the maximum D in this case is min(W/2, H / (π + 1)) and X = D is suitable X for this D.
We see that this case corresponds to vertical alignment of circles.
Now assume that D > W/2.
This case is possible only when Hp := H / (π + 1) > W/2 since D ≤ Hp (see above).
In view of condition X ≥ D, the above inequality on X is equivalent to
X ≥ D + sqrt(W * (2 * D − W)).
Summarizing we need to find the maximum D such that W/2 < D ≤ min(H / (π + 1), W) for which there exists X such that
- 0 < X < H,
- D ≤ X ≤ H − π * D,
- D + sqrt(W * (2 * D − W)) ≤ X.
It is clear that existing of such X is equivalent to
D + sqrt(W * (2 * D − W)) ≤ H − π * D.
In view of D ≤ H / (π + 1) this equivalent to
W * (2 * D − W) ≤ (H − (π + 1) * D)2.
After some calculations we get
D2 − 2 * (H / (π + 1) + W / (π + 1)2) * D + (H2 + W2) / (π + 1)2 ≥ 0.
Setting Wp := W / (π + 1)2 and recalling the definition of Hp we arrive at
D2 − 2 * (Hp + Wp) * D + (Hp2 + W * Wp) ≥ 0.
Discriminant is Wp * (Wp + 2 * Hp − W) and positive in view of condition 2 * Hp > W.
Hence this inequality is equivalent to:
either D ≤ D0 := Hp + Wp − sqrt(Wp * (Wp + 2 * Hp − W)) or D ≥ Hp + Wp + sqrt(Wp * (Wp + 2 * Hp − W)).
But second case violates condition D ≤ Hp.
Hence, maximum value of D for which there exists proper value of X is
D = min(W, Hp, D0) provided that it is > W/2.
But formula for D0 and condition 2 * Hp > W imply D0 ≤ Hp, so we can rewrite the answer as D = min(W, D0).
Summarizing the entire analysis leads to the following formula for maximum D:
Denote Hp = H / (Pi + 1) and Wp = W / (Pi + 1)^2.
Then the maximum D is max(min(W/2, Hp), D1), where D1 = 0 if W/2 > Hp and
D1 = min(W, Hp + Wp - sqrt(Wp * (Wp + 2 * Hp - W))) otherwise.
And you can find exactly this formulas implemented in the author’s solution.
ALTERNATIVE SOLUTION 2:
Actually it is possible to solve the problem without calculating V(W, H) and V(H, W) separately.
At first swapping W and H if necessary we can assume that W ≤ H. Then the answer can be found as follows:
ans = π/4 * max(DH * DH * (W − DH), DW * DW * (H − DW), Dtricky * Dtricky * W),
where DH = H / (π + 1), DW = W / (π + 1), and Dtricky is maximum D mentioned in the QUICK EXPLANATION section in the second case (when W is the height of the cylinder).
Refer two the tester’s solution as an exact implementation of this idea (but be careful − he swaps roles of W and H).
Since editorial is already rather long the proof is omitted and we leave it as an exercise.
OPEN PROBLEMS:
Till the very beginning of the contest there were no restriction that lateral surface should be cut parallel to the sides of the second rectangle, since we believe that it is always optimal to cut it so. But we can’t find the proof of this and hence had to add this restriction. If someone knows either the proof or counter-example to the "without parallel restriction’ version we would like to see it.
At some point I also think on version where there is no initial cut and we simply need to cut all three pieces from the initial rectangle, but this version seems much more complicated. I still have feeling that the current solution is optimal even for such version but I could be wrong. Again if someone knows either the proof or counter-example to this general version we would like to see it, or if it is really interesting and challenging then that someone could set the new problem 
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
RELATED PROBLEMS:
e-olimp - 889 - Cylinder
The current problem is inspired by this problem several years ago but only now I finally set it up
that was great 
We want more problems from you. More mathematics man!