сдвигаться в сторону центра то с одной, то с другой стороны
А вдруг в центре сталактит, упирающийся в пол?
Кстати, всё, что ниже него, входит во все возможные прямоугольники. Это даёт идею решения: выбираем самый низкий("длинный") сталактит, поднимаем дно до него, вся пещера разбивается на две, их рассматриваем по отдельности таким же образом.