Find the minimum lantern radius needed to illuminate an entire street segment.
Problem
A street has length and there are lanterns placed at distinct positions along it. Each lantern illuminates a segment of the street centered at its position with radius .
Your task is to determine the smallest radius such that the whole street from position $0L$ is illuminated.
More precisely, every point on the segment must lie within distance at most from at least one lantern.
Key idea
The street is fully covered when:
- the beginning of the street is covered by the first lantern,
- the end of the street is covered by the last lantern,
- and every gap between neighboring lanterns is covered by expanding from both sides.
Return the minimum radius required.
Input Format
- The first line contains two integers and .
- The second line contains integers giving the positions of the lanterns along the street.
Output Format
- Print one floating-point number: the minimum radius required to cover the entire street.
Constraints
- Lantern positions are distinct.
- The answer should be accurate within a small floating-point error.
Example 1
Input
7 15 15 5 3 7 9 14 0
Output
2.5000000000
Explanation
After sorting the lantern positions, the largest uncovered gap between adjacent lanterns is 5, so half of that is 2.5. The street endpoints are also covered, and the maximum required radius is 2.5.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.