Падающий лёд
Представьте, что ледяные диски падают один за другим в коробку, каждый из них достигает самой нижней точки, до которой он может добраться, не перекрывая и не перемещая предыдущие диски. Каждый диск затем замерзает на месте, так что его нельзя сдвинуть последующими дисками. Ваша задача — определить общую высоту конечной комбинации дисков.
Чтобы ответ был уникальным, предположим, что любой диск, достигающий дна коробки, катится как можно дальше влево. Также данные выбраны так, что для любого диска, который не достигает дна, будет уникальная самая низкая позиция. Данные также таковы, что нет "идеальных совпадений": каждый диск, который приземляется, будет контактировать только с двумя другими точками, на предыдущих кругах или на сторонах коробки. Иллюстрации выше показывают белые заполненные диски, пронумерованные в порядке, в котором они падают в свои коробки. Серая окружность на четвертой иллюстрации не предназначена для того, чтобы быть диском, который упал. Серый диск включен, чтобы продемонстрировать точку: серый диск того же размера, что и диск 2, так что есть место для диска 2 на самом дне его коробки, но диск 2 не может достичь этой позиции, падая сверху. Он застревает на диске 1 и стороне коробки.
Один из способов найти верхнюю точку пересечения двух пересекающихся окружностей следующий. Предположим, что окружность 1 имеет центр (x_1,y_1) и радиус r_1, и предположим, что окружность 2 имеет центр (x_2, y_2) и радиус r_2. Также предположим, что окружность 1 находится левее окружности 2, т.е. x_1 < x_2. Пусть
dx = x_2 - x_1,dy = y_2 - y_1,D = sqrt(dx*dx + dy*dy),E = (r_1*r_1 - r_2*r_2 + D*D)/(2*D),F = sqrt(r_1*r_1 - E*E);
тогда верхняя точка пересечения будет (x_1 + (E*dx - F*dy)/D, y_1 + (F*dx + E*dy)/D).
Входные данные
Входные данные состоят из одного или нескольких наборов данных, за которыми следует строка, содержащая только 0, что сигнализирует об окончании ввода. Каждый набор данных находится на отдельной строке и содержит последовательность из трех или более положительных целых чисел, разделенных пробелами, в формате w, n, d_1, d_2, d_3, ..., d_n, где w — ширина коробки, n — количество дисков, а оставшиеся числа — диаметры дисков, в порядке их падения в коробку. Можно предположить, что w < 100, что n < 10, и что каждый диаметр меньше w.
Выходные данные
Для каждого набора данных выведите одну строку, содержащую высоту стопки дисков, округленную до двух знаков после запятой.