Падіння льоду

Уявіть, що диски з льоду падають один за одним у коробку, кожен зупиняється в найнижчій точці, яку він може досягти без перекриття або переміщення попередніх дисків. Кожен диск потім замерзає на місці, тому його не можуть зрушити наступні диски. Ваше завдання - знайти загальну висоту кінцевої комбінації дисків.

Щоб відповідь була унікальною, припустимо, що будь-який диск, який досягає дна коробки, котиться якомога далі вліво. Також дані обрані так, що буде унікальне найнижче положення для будь-якого диска, який не досягає дна. Дані також такі, що немає "ідеальних відповідностей": кожен диск, що приземляється, буде контактувати лише з двома іншими точками, на попередніх колах або на боках коробки. Ілюстрації вище показують білі заповнені диски, позначені порядком, у якому вони падають у свої коробки. Сірий круг на четвертій ілюстрації не призначений для того, щоб бути диском, що впав. Сірий диск включено, щоб продемонструвати точку: сірий диск такого ж розміру, як диск $2$, тому є місце для диска $2$ на самому дні його коробки, але диск $2$ не може досягти цього положення, падаючи зверху. Він застряє на диску $1$ та на боці коробки.

Один зі способів знайти верхню точку перетину двох пересічних кіл такий. Припустимо, що коло $1$ має центр (x_1, y_1) і радіус r_1, і припустимо, що коло $2$ має центр (x_2, y_2), і радіус r_2. Також припустимо, що коло $1$ знаходиться лівіше кола $2$, тобто x_1 < x_2. Нехай

тоді верхня точка перетину буде (x_1 + (E \cdot dx - F \cdot dy)/D, y_1 + (F \cdot dx + E \cdot dy)/D).