Задача D. "Архитектор Вася"

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

Как известно, существует 2 условия равновесия тела (здесь и далее будем считать устойчивое и неустойчивое равновесие неразличимыми, и называть общим словом "равновесие" или "устойчивость", так как в данной задаче нет никакого внешнего воздействия на конструкцию, кроме естесственной силы тяжести и силы взаимодействия кубиков с друг другом), но нам в этой задаче надо будет рассмотреть второй закон равновесия, который мы переформулируем в критерий устойчивости для нашей задачи:

Система кубиков устойчива тогда и только тогда, когда для любой ее точки сумма моментов всех сил, приложенных к этой точке равна нулю. Несложно понять, что это утверждение эквивалентно тому, что система кубиков устойчива тогда и только тогда, когда проекция центра масс этой системы лежит внутри или на границе проекции опоры, на которой расположена эта система кубиков.

Значит, используя этот критерий, будем решать задачу следующим образом: будем в текущую башенку добавлять по одному кубику и проверять, устойчива ли она. Для этого, мы должны проверить, является любой суффикс текущей башенки устойчивым, для этого найдем его центр масс, и проверим критерий. Если он не выполняется, то башенка разрушится, и выведем ее высоту минус один, а если она вся целиком устойчива, то надо вывести число n.

Приведем формулы для координат центра масс некоторых n кубиков:

где:
,
m_i = |x_i, 1 - x_i, 2|³ = |y_i, 1 - y_i, 2|³