Don't Burst the Balloon
Time limit7sMemory limit128 MB
Find the largest radius of a sphere resting on the floor of a square box with vertical needles that avoids the walls and needles.
- Level
Medium7 of 10
- Topics
- Geometry, Binary search
- Solved
- No attempts yet
Problem
An open-top box with a square bottom sits on the floor. Look inside and you see a few needles standing vertically on the bottom.
You want to put a spherical balloon into this box. The balloon has to touch the bottom of the box, and it may not cut into any of the four side walls or into a needle. Surfaces that only graze each other are fine. Find the radius of the largest such balloon.
The side walls are tall and have no thickness. A balloon with a radius larger than can therefore bulge out over a wall, and in that case the top edge of the wall is what blocks it.

The upper part of the figure is a layout of needles and the lower part is the largest balloon that fits that layout. It is the first dataset of the example input.
Input
The input is a sequence of datasets. Each dataset has the following format.
n w
x1 y1 h1
.
.
.
xn yn hn
The first line holds two positive integers and separated by one space. is the number of needles and is the height of the side walls.
The bottom of the box is a square with side 100, and its four corners are at , , , .
Each of the next lines holds three integers , , . The -th needle stands at and its height is . No two needles stand at the same position.
, , , , . Ignore the thickness of the needles and of the walls.
The last line of the input holds two zeros. The number of datasets does not exceed 1000.
Output
For each dataset, print the radius of the largest balloon on one line.
The judge compares output text exactly. Round the radius at the sixth decimal place and print five digits after the decimal point. A radius of 26 is printed as 26.00000. Every answer in the test data stays farther than from a rounding boundary, so a radius computed within an error of fixes the output uniquely.