This page is still under construction.

Parts of this page are still being built. What you see may change.

Don't Burst the Balloon

Time limit7sMemory limit128 MB

Summary
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 ww tall and have no thickness. A balloon with a radius larger than ww 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 nn and ww separated by one space. nn is the number of needles and ww is the height of the side walls.

The bottom of the box is a square with side 100, and its four corners are at (0,0,0)(0, 0, 0), (0,100,0)(0, 100, 0), (100,100,0)(100, 100, 0), (100,0,0)(100, 0, 0).

Each of the next nn lines holds three integers xix_i, yiy_i, hih_i. The ii-th needle stands at (xi,yi,0)(x_i, y_i, 0) and its height is hih_i. No two needles stand at the same position.

1≤n≤101 \le n \le 10, 10≤w≤20010 \le w \le 200, 0<xi<1000 < x_i < 100, 0<yi<1000 < y_i < 100, 1≤hi≤2001 \le h_i \le 200. 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 10−610^{-6} from a rounding boundary, so a radius computed within an error of 10−710^{-7} fixes the output uniquely.

Examples1

  1. Example 1

    Input
    5 16
    70 66 40
    38 52 20
    40 35 10
    70 30 10
    20 60 10
    1 100
    54 75 200
    1 10
    90 10 1
    1 11
    54 75 200
    3 10
    53 60 1
    61 38 1
    45 48 1
    4 10
    20 20 10
    20 80 10
    80 20 10
    80 80 10
    0 0
    
    Expected output
    26.00000
    39.00000
    130.00000
    49.49777
    85.00000
    95.00000