Задача COOKIES. Бабушка готовила печенье. Для этого она раскатала тесто в большой пласт в форме круга и стаканчиками различных диаметров выдавила в нём круглые кусочки, чтобы потом запечь их и получить из них вкусное печенье. Известно, что никакие два круглых выреза не пересекаются между собой, кроме того, все вырезы полностью содержатся внутри пласта теста. Однако вырезы могут касаться друг друга и края пласта теста.
Любимый внук из корыстных соображений решил помочь бабушке: он решил выдавить в оставшейся части пласта круглую заготовку для печенья как можно большего размера. Однако он не знает, какой диаметр должен быть у стаканчика, которым нужно выдавливать такую заготовку. Помогите ему.
Технические условия: Напишите программу COOKIES, которая читает с устройства стандартного ввода размеры пласта теста, а также положение и размеры вырезанных заготовок, и выводит на устройство стандартного вывода радиус максимальной по размеру заготовки, которую еще можно вырезать из этого пласта теста.
В первой строке данных находится действительное число R – радиус пласта теста. Считается, что центр пласта находится в начале координат – в точке с координатами (0,0). Вторая строка содержит число N – количество уже вырезанных заготовок. Следующие N строк содержат по 3 действительных числа xk, yk, rk – координаты центра и радиус очередного выреза (k = 1, 2,..., N).
Единственная строка вывода должна содержать искомый радиус максимальной по размеру заготовки, которую еще можно вырезать из пласта теста. Ответ не должен отличаться от правильного больше, чем на =10-3.
Ограничения: 0.0 < R <=1000.0, 1 <= N <= 100.
Пример: смотри рисунок
|
Ввод 1.01 |
Вывод 0.666666 |