eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Don`t Burst the Balloon

Don`t Burst the Balloon

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. \textit{\textbf{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. \InputFile The input is a sequence of datasets. Each dataset is formatted as follows. \textbf{n w} \textbf{x_1 y_1 h_1} \textbf{...} \textbf{x_n y_n h_n} The first line of a dataset contains two positive integers, \textbf{n} and \textbf{w}, separated by a space. \textbf{n} represents the number of needles, and \textbf{w} represents the height of the side walls. The bottom of the box is a \textbf{100}×\textbf{100} square. The corners of the bottom face are placed at positions (\textbf{0}, \textbf{0}, \textbf{0}), (\textbf{0}, \textbf{100}, \textbf{0}), (\textbf{100}, \textbf{100}, \textbf{0}), and (\textbf{100}, \textbf{0}, \textbf{0}). Each of the \textbf{n} lines following the first line contains three integers, \textbf{x_i}, \textbf{y_i}, and \textbf{h_i}. (\textbf{x_i}, \textbf{y_i}, \textbf{0}) and \textbf{h_i} represent the base position and the height of the \textbf{i}-th needle. No two needles stand at the same position. You can assume that \textbf{1} ≤ \textbf{n} ≤ \textbf{10}, \textbf{10} ≤ \textbf{w} ≤ \textbf{200}, \textbf{0} < \textbf{x_i} < \textbf{100}, \textbf{0} < \textbf{y_i} < \textbf{100} and \textbf{1} ≤ \textbf{h_i} ≤ \textbf{200}. 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 \textbf{1000}. \includegraphics{https://static.e-olymp.com/content/91/91a85687ae74bf73c67ddcd042ec74a4d6a2425d.jpg} \textit{\textbf{Figure 1}}. The upper shows an example layout and the lower shows the largest spheric balloon that can be placed. \OutputFile 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 \textbf{0.0001}.
Лимит времени 30 секунд
Лимит использования памяти 256 MiB
Входные данные #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
Выходные данные #1
26.00000
39.00000
130.00000
49.49777
85.00000
95.00000
Источник ACM International Collegiate Programming Contest, Asia Regional Contest, Aizu, 2013–11–24