Вечерний пейзаж города К

Известный блогер и урбанист Варлам Ильин приехал в город К., известный не очень благопри- ятной экологической обстановкой.

В качестве завершающей фотографии к очередной заметке для блога Варлам хочет поместить фотографию заходящего солнца на фоне индустриального пейзажа, причём видимой должна быть ровно половина диска солнца.

Осталось только выбрать момент...

Пусть горизонт проходит по оси X, солнце представляется кругом постоянного радиуса с центром на оси Y, а при заходе солнца центр круга двигается по оси Y из плюс бесконечности вниз до тех пор, пока солнце целиком не скроется за горизонтом.

Индустриальный пейзаж, найденный Варламом, можно представить в виде совокупности зданий – прямоугольников со сторонами, параллельными координатным осям, у которых основания лежат на линии горизонта, все точки имеют неотрицательную y-координату. Прямоугольники могут касаться, но не могут иметь общих внутренних точек.

Видимой является та часть солнца, которая находится над горизонтом и не закрыта зданиями.

Требуется найти значение высоты центра солнца над горизонтом (координаты y_s), при котором видимой будет ровно половина диска.

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа – количество N зданий, формирующих индустриальный пейзаж, и радиус R круга, представляющего солнце (0 ≤ N ≤ 100, 1 ≤ R ≤ 100).

Каждая из последующих N строк содержатся три целых числа – x-координата нижнего левого угла i-го здания x_i (–100 ≤ x_i ≤ 100), ширина i-го здания w_i (1 ≤ w_i ≤ 100) и высота i-го здания h_i (1 ≤ h_i ≤ 100), тем самым каждое здание представляет собой прямоугольник с вершинами в точках (x_i,0), (x_i,h_i), (x_i + w_i,h_i), (x_i + w_i,0).

Гарантируется, что здания идут слева направо (x_i < x_i+1), что силуэты зданий не пересекаются (x_i + w_i ≤ x_i+1), что высоты двух крайних зданий не превосходят R и что разность высот любых двух соседних зданий по абсолютной величине не превосходит R.

Выходные данные

В выходной файл OUTPUT.TXT выведите наибольшее значение высоты солнца над горизонтом, при котором видимой будет ровно половина солнечного диска, с абсолютной погрешностью, не худшей чем 10^-6.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]