Angry Cows (Gold)#10598
Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows". The premise, which she believes is completely original, is that the player launches a cow with a slingshot into a one-dimensional scene consisting of a set of hay bales located at various points on a number line. The cow lands with sufficient force to detonate the hay bales in close proximity to her landing site, which in turn may set off a chain reaction causing additional hay bales to explode. The goal is to use a single cow to start a chain reaction that detonates all the hay bales.
There are hay bales located at distinct integer positions x_1, x_2, \ldots, x_n on the number line. If a cow is launched with power and lands at position , she creates a blast with radius , engulfing all hay bales within the interval [x - r, x + r]. These hay bales then explode themselves (all simultaneously), each with a blast radius of r - 1. Any hay bales that have not yet exploded but are caught in these blasts then explode (all simultaneously) with a blast radius of r - 2, and so on.
Determine the minimum amount of power with which a single cow can be launched so that, if she lands at an appropriate location, she will eventually cause every hay bale in the scene to explode.
The first line contains an integer n~(2 \le n \le 50000). The next lines each contain an integer x_i~(0 \le x_i \le 10^9), specifying the position of one hay bale on the number line.
Print the minimum power with which a cow must be launched in order to detonate all the hay bales. The answer should be rounded and printed to exactly decimal place.
In this example, a cow launched with power at, say, position , will immediately detonate the hay bales at positions and . These bales then explode simultaneously, each with a blast radius of , engulfing the bales at positions and . These bales next explode simultaneously with a blast radius of , engulfing the final bale at position , which finally explodes with a blast radius of .
Example 1