Перед тем, как перейти к алгоритму, отметим, что ответом на задачу будет отношение суммарной площади всех прямоугольников к площади объединения всех прямоугольников.
Чтобы понять это, сделаем следующее наблюдение. В первую очередь понятно, что если все прямоугольники совпадают, то ответом будет их количество. Теперь временно забудем про то, что фигуры должны быть прямоугольниками, предположим, что форма фигур на входе может быть любой, и покажем как построить пример, где площать объединения была бы s и ожидаемое среднее количество проткнутых фигур было бы e. Понятно, что такой пример можно построить начав с произвольного контура объединения, ограничевающего площать s, путём добавления дополнительных фигур, лежащих внутри этого контура. Суммарно необходимо будет добавить фигур на общую площать t = s· (e - 1), но конкретное число не важно. Важно то, что взаимное расположение этих добавленных фигур не имеет значения, и, соответственно, ответ на исходную задачу зависит только от площади контура объединения всех фигур и суммарной площади всех фигур.
Вернёмся теперь к прямоугольникам. Найти суммарную площадь всех прямоугольников легко. Сложно найти площадь объединения всех прямоугольников быстрее, чем за O(n3). Обратите внимание, что объединение может состоять из множества несвязных компонент, компоненты не обязаны быть выпуклыми, они могут содержать дырки, и вообще, в общем случае описать объединение всех входных прямоугольников не очень просто. К счастью, в этой задаче нас интересует только площать этого объединения.
Одно из решений, которое относительно несложно закодировать, заключается в следующем. Будем считать площадь объединения методом трапеций. Отметим сразу, что для вычисления площади методом трапеций достаточно знать все ориентированные сегменты контура, а их порядок совершенно не важен. Таким образом достаточно "просто" найти все ориентированные сегменты, которые образуют контур объединения, причём вертикальные сегменты могут быть сразу исключены из рассмотрения.
Например, если для какого-то теста объединение представляет собой фигуру с дыркой, то внешний контур должен превратиться во множество сегментов с положительной общей площадью, а внутренний контур --- во множество сегментов с отрицательной общей площадью. Иными словами, внешний контур следует обойти по часовой стрелке, а внутренний --- против часовой стрелки.
Для того, чтобы найти все такие сегменты, рассмотрим все различные невертикальные прямые, на которых лежат стороны входных квадратов. Их не больше, чем 4n. Понятно, что каждый сегмент объединения лежит на одной из этих прямых, соответственно, достаточно проверить отдельно каждую из прямых, но только по одному разу.
Правила, по которым можно выделить "положительные" и "отрицательные" сегменты на каждой прямой достаточно просты:
1) Если сегмент этой прямой (x1, y1) - (x2, y2) является частью границы одного из входных прямоугольников, тогда помечаем этот сегмент как "положительный" или "отрицательный" в зависимости от того, лежит ли данный прямоугольник выше или ниже прямой.
2) Если на сегменте этой прямой (x1, y1) - (x2, y2) накладываются границы двух входных прямоугольников, лежащих по разные стороны от прямой, то этот сегмент не може являться частью контура.
3) Если сегмент (x1, y1) - (x2, y2) лежит полностью внутри какого-то из входных прямоугольников, то он не может являться частью контура.
Соответственно, построить все сегмента контура объединения можно с помощью примерно следующего кода:
для каждой уникальной не-вертикальной прямой
создаём массив маркеров. маркер хранит x-координату и одно из четырёх событий: { начало/конец положительного сегмента, начало/конец отрицательного сегмента }
проходим во всем входным прямоугольникам
если одна из сторон этого прямоугольника принадлежит рассматриваемой прямой
добавляем два маркера: начало и конец сегмента. знак сегмента определяется положением прямоугольника относительно рассматриваемой прямой.
иначе если это прямоугольник пересекается с прямой
находим левую и правую точки пересечения, и помечаем сегмент между ними четырьмя маркерами, покрывая его и положительным и отрицательным сегментом.
сортируем массив маркеров по их x-координате
идём по маркерам слева направо. если про какой-то сегмент известно, что он должен быть положительным, и не должен быть отрицательным, выводим его как положительный сегмент финального контура. если известно, что он должен быть отрицательным и не должен быть положительным, выводим его как отрицательный сегмент финального контура.
После этого можно было бы выписать множество финальных контуров используя, например, поиск в глубину, но для метода трапеций это не требуется. Достаточно просуммировать (x2 - x1)· (y1 + y2) / 2 для каждого сегмента.
Вышеописанное решение работает за O(n2· logn) : для каждой из O(n) прямых мы рассматриваем O(n) пересечений, и их сортировка занимает O(n· logn) на каждую прямую.