Welcome to ZOJ
129 - ZOJ Monthly, December 2013 - C
Cut the Cake

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

Bob has a circular cake whose radius is R. He puts it on 2D-plane and the centre of the cake is on coordinate origin O. We know different part of a cake tastes differently. In this cake, Bob use ρ(x, y) = Ax2 + By2 to describe the taste of point (x, y) on the cake.

Now Bob wants to cut the cake into several parts. And he found two kinds of knives in his kitchen. So he decided to use those knives to cut. The Following are the shape and usages of the knives:

  • Circular knife: the radius is r ( r = 1, 2, ..., or R-1 ). These knives can cut the cake along the red circle in Figure 1.
  • Linear knife: the length is R. There knives can cut the cake along the blue half-line whose start point is the coordinate origin O in Figure 1.

From the description, we know Bob has R types of knives and he can cut the cake at most R+11 times.

Well, let's assume Bob uses Circular knife a times and Linear knife b times. Apparently, the cake is divided into N = b×(a + 1) parts. Bob uses Si to describ the taste of i-th part which is the surface integral of the taste on this part. Bob wants the differences of the taste of the N parts as small as possible. He has learned some math and he knows if the root mean square error of Si is small, the differences are small as well.

Now, Bob can cut the cake exactly K times. He wants to know what's the minimal value of the mean square error of Si.

Note: In Figure 1, R is 6 and the radian between any adjacent blue line is π/6. And Figure 2 is an example that R = 6, a = 3 and b = 6.


Input will consist of multiple test cases. Each case contains one line with four integers, R ( 1 ≤ R ≤ 100 ), A ( 0 ≤ A ≤ 9 ), B ( 0 ≤ B ≤ 9 ), K ( 0 ≤ K < R + 12 ).


Please output the corresponding minimal value of the root mean square error, one line for one case. Any solution with a relative or absolute error of at most 1e-5 will be accepted.

Sample Input

1 1 1 4
5 6 7 8

Sample Output



The root mean square error of a sequence { S1, S2, ..., SN } is:

the formula of the mean square error

In the first sample, Bob just uses Linear knife 4 times and divides the cake into 4 parts. All the 4 parts have the same taste, so the minimal value of σ is 0.

Author: LIN, Xi
Submit    Status