804. Slicing the Pies
There are n round pies, all the same thickness; pie i has radius r[i]. A party of
f friends plus yourself, so f + 1 people in all, must each get a slice of exactly the same
area. A slice has to come from ONE pie, so two leftover wedges cannot be pushed together, and
leftovers are thrown away.
Print the largest area one person can be given, to exactly 4 digits after the decimal point.
pies 4 3 3, f = 3 -> 25.1327
pies 1 1, f = 3 -> 1.5708
pies 5, f = 24 -> 12.5664
With radii 4, 3 and 3 and four people, the first pie has area 16 * pi and yields two slices of
25.1327, while each of the other two yields one. That is four slices.
## What value of pi to use
Use the constant your language provides: math.pi in Python, M_PI or acos(-1.0) in C and
C++, Math.PI in Java, Math.PI in JavaScript. All of these are the same double, so all five
agree to the last bit. Writing 3.14159 by hand changes the fourth decimal of the answer and
fails.
## Why the greedy answers are wrong
Handing out the biggest pies first and dividing what is left does not work, because a pie cut into
two gives two slices of half its area and a pie cut into three gives three of a third, and which
split is best depends on the area chosen, not on the pie. Sorting and taking the top f + 1 pies
fails whenever there are fewer pies than people.
## What a candidate answer buys you
Fix an area A. Pie i yields floor(area[i] / A) whole slices of that size, because the rest
is waste. Add those up and compare with f + 1:
slices(A) = floor(pi*r[0]^2 / A) + ... + floor(pi*r[n-1]^2 / A)
## Why the predicate is monotone
A larger A divides into each pie fewer times, and flooring keeps that, so slices is
non-increasing in A. The workable areas form an initial stretch and the answer is where it
ends.
## The bounds
lo = 0 and hi = pi * max(r)^2, the largest single pie. Nobody can receive more than one whole
pie, since a slice comes from one pie only.
## The boundary that breaks a careless implementation
Everybody, yourself included, has to be fed. The party is f + 1 people and not f, and a check
that compares against f hands out slices that are too big by exactly one person's worth. The
test with f = 0 is there to catch it: one person, and the answer is the whole largest pie.
The second is precision. Areas reach pi * 10^6, around 3.14 * 10^6, and four decimals on top
of seven digits is eleven significant figures. A double carries about sixteen, so the fixed
hundred halvings land far inside the printed precision, but only if the count loop stops early
rather than accumulating millions of terms.
## Related problems
Problem 803 runs the same counting argument on lengths, and problem 765 is the whole-number version of that. Problem 806 also divides a quantity into equal real parts, but minimises the part size instead of maximising it.
## Cost
Time O(100 * n). Space O(n).
Constraints - `1 ≤ n ≤ 10000` - `0 ≤ f ≤ 9999` - `1 ≤ r[i] ≤ 1000` - take pi to be the double constant your language provides - every answer is at least `10^-9` away from a halfway rounding point at 4 digits
Input
The first line contains two integers n and f, the number of pies and the number of friends.
The second line contains n integers r[0] ... r[n-1], the radii of the pies.
Output
Print the largest area one person can receive with exactly 4 digits after the decimal point, in plain fixed notation and never in exponent form, alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.