eolymp
bolt
Try our new interface for solving problems
Məsələlər

Don`t Burst the Balloon

Don`t Burst the Balloon

Zaman məhdudiyyəti 30 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

An open-top box having a square bottom is placed on the floor. You see a number of needles vertically planted on its bottom.

You want to place a largest possible spheric balloon touching the box bottom, interfering with none of the side walls nor the needles.

Java Specific: Submitted Java programs may not use "java.awt.geom.Area". You may use it for your debugging purposes.

Figure 1 shows an example of a box with needles and the corresponding largest spheric balloon. It corresponds to the first dataset of the sample input below.

Giriş verilənləri

The input is a sequence of datasets. Each dataset is formatted as follows.

n w

x_1 y_1 h_1

...

x_n y_n h_n

The first line of a dataset contains two positive integers, n and w, separated by a space. n represents the number of needles, and w represents the height of the side walls.

The bottom of the box is a 100×100 square. The corners of the bottom face are placed at positions (0, 0, 0), (0, 100, 0), (100, 100, 0), and (100, 0, 0).

Each of the n lines following the first line contains three integers, x_i, y_i, and h_i. (x_i, y_i, 0) and h_i represent the base position and the height of the i-th needle. No two needles stand at the same position.

You can assume that 1n10, 10w200, 0 < x_i < 100, 0 < y_i < 100 and 1h_i200. You can ignore the thicknesses of the needles and the walls.

The end of the input is indicated by a line of two zeros. The number of datasets does not exceed 1000.

Figure 1. The upper shows an example layout and the lower shows the largest spheric balloon that can be placed.

Çıxış verilənləri

For each dataset, output a single line containing the maximum radius of a balloon that can touch the bottom of the box without interfering with the side walls or the needles. The output should not contain an error greater than 0.0001.

Nümunə

Giriş verilənləri #1
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
Çıxış verilənləri #1
26.00000
39.00000
130.00000
49.49777
85.00000
95.00000
Mənbə ACM International Collegiate Programming Contest, Asia Regional Contest, Aizu, 2013–11–24