Тем более, что без нее она делается за O(N log^2(N)) стандартными методами (при помощи двумерного дерева отрезков).
1) Точно-точно O(N log^2(N)) ? Я что-то не вижу гарантий, почему оное двумерное дерево отрезков всегда можно сделать с кол-вом узлов O(N), а не вплоть до theta(N^2). А алгоритмы, в которых оценка памяти больше оценки времени, всегда настораживают -- кто гарантирует инициализацию?
2) Количество кода (в строках и байтах)? В моём коде 2006 года 60 непустых строк, 1758 байт -- при том, что всё это на ФриПаскале, где самому писать минимум и максимум, и вообще не_очень экономно написано. См. http://ideone.com/JASqa
Да и не понятно, откуда берется 2^(N/10) в асимптотике. Почему там не чистое 2^N?
Повторю ещё раз -- благодаря тому, что в условии написано, что не более чем 10% параллелепипедов пересекаются более чем по 2 одновременно. А также благодаря тому, что принцип реализован рекурсивно, с проверками, а не пусто ли текущее пересечение (в этом случае, естесно, вся ветка рекурсии отсекается).
Разумеется, именно в данной задаче оно немного неестественно. Но вообще говоря -- почему бы и нет? Что принципиально неестественного в том, что далеко не все 2^N пересечений действительно непусты?