Не лусни кульку
Відкрита коробка з квадратним дном стоїть на підлозі. На її дні вертикально встановлено ряд голок.
Ваша задача — розмістити найбільшу можливу сферичну повітряну кулю, яка торкається дна коробки, не зачіпаючи жодної з бічних стінок або голок.
Специфічно для Java: програми на Java не можуть використовувати "java.awt.geom.Area". Ви можете використовувати це для цілей налагодження.
Рисунок 1 демонструє приклад коробки з голками та відповідну найбільшу сферичну кулю. Це відповідає першому набору даних з наведеного нижче прикладу вхідних даних.
Вхідні дані
Вхідні дані складаються з кількох наборів. Кожен набір даних має такий формат:
n w
x_1 y_1 h_1
...
x_n y_n h_n
Перша строка набору даних містить два додатні цілі числа, n та w, розділені пробілом. n — це кількість голок, а w — висота бічних стінок.
Дно коробки є квадратом розміром 100×100. Кути нижньої грані розташовані в точках (0, 0, 0), (0, 100, 0), (100, 100, 0) та (100, 0, 0).
Кожна з n наступних строк містить три цілі числа: x_i, y_i та h_i. (x_i, y_i, 0) — це базова позиція, а h_i — висота i-ї голки. Жодні дві голки не мають однакової позиції.
Ви можете припустити, що 1 ≤ n ≤ 10, 10 ≤ w ≤ 200, 0 < x_i < 100, 0 < y_i < 100 та 1 ≤ h_i ≤ 200. Товщину голок та стінок можна ігнорувати.
Кінець вхідних даних позначається строкою з двома нулями. Кількість наборів даних не перевищує 1000.
Рисунок 1. Верхня частина показує приклад розташування, а нижня — найбільшу сферичну кулю, яку можна розмістити.
Вихідні дані
Для кожного набору даних виведіть один рядок, що містить максимальний радіус кулі, яка може торкатися дна коробки, не зачіпаючи бічні стінки або голки. Вихід не повинен містити помилку більше ніж 0.0001.