Падіння льоду
Уявіть, що диски з льоду падають один за одним у коробку, кожен зупиняється в найнижчій точці, яку він може досягти без перекриття або переміщення попередніх дисків. Кожен диск потім замерзає на місці, тому його не можуть зрушити наступні диски. Ваше завдання - знайти загальну висоту кінцевої комбінації дисків.
Щоб відповідь була унікальною, припустимо, що будь-який диск, який досягає дна коробки, котиться якомога далі вліво. Також дані обрані так, що буде унікальне найнижче положення для будь-якого диска, який не досягає дна. Дані також такі, що немає "ідеальних відповідностей": кожен диск, що приземляється, буде контактувати лише з двома іншими точками, на попередніх колах або на боках коробки. Ілюстрації вище показують білі заповнені диски, позначені порядком, у якому вони падають у свої коробки. Сірий круг на четвертій ілюстрації не призначений для того, щоб бути диском, що впав. Сірий диск включено, щоб продемонструвати точку: сірий диск такого ж розміру, як диск 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.
Вихідні дані
Для кожного набору даних виведіть один рядок, що містить висоту купи дисків, округлену до двох знаків після коми.