페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3953

Angry Cows 2초 512MB

문제

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 shoots 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 might set of a chain reaction that causes 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 N 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 R landing at position x, this will causes a blast of "radius R", engulfing all hay bales within the range x-R \ldots x+R. These hay bales then themselves explode (all simultaneously), each with a blast radius of R-1. Any not-yet-exploded bales caught in these blasts then all explode (all simultaneously) with blast radius R-2, and so on.

Please determine the minimum amount of power R with which a single cow may be launched so that, if it lands at an appropriate location, it will cause subsequent detonation of every single hay bale in the scene.

Problem credits: Brian Dean


입력

The first line of input contains N (2 \leq N \leq 50,000). The remaining N lines all contain integers x_1 \ldots x_N (each in the range 0 \ldots 1,000,000,000).


출력

Please output the minimum power R with which a cow must be launched in order to detonate all the hay bales. Answers should be rounded and printed to exactly 1 decimal point.


예제1

입력
5
8
10
3
11
1
출력
3.0

In this example, a cow launched with power 3 at, say, location 5, will cause immediate detonation of hay bales at positions 3 and 8. These then explode (simultaneously) each with blast radius 2, engulfing bales at positions 1 and 10, which next explode (simultaneously) with blast radius 1, engulfing the final bale at position 11, which finally explodes with blast radius 0.


출처

USACO 2016 January Gold

역링크 공식 문제집만