Szukałem dużo, ale nie znalazłem dobrej odpowiedzi, która działa w tym przypadku. Mamy kilka prostokątów, które są poziome lub pionowe. Można je losowo umieścić na stronie. Mogą zachodzić na siebie lub mieć wspólną krawędź lub być oddzielone od siebie. Chcę znaleźć algorytm z O (nlogn), który może znaleźć obwód i obszar tych prostokątów. Te zdjęcia mogą wyjaśnić problem.

Myślę, że drzewa interwałowe mogą pomóc, ale nie wiem jak.