P1856 [IOI 1998 / USACO5.5] Rectangle Perimeter Picture

There are many rectangular posters and photos on a wall. Their edges are horizontal and vertical. Each rectangular picture may partially or completely cover other pictures. The length of the boundary of the union of all rectangles is called the perimeter.

Write a program to compute the perimeter.  The $7$ rectangles are shown in Figure 1.  The boundary of the union of all rectangles is shown in Figure 2. All rectangle vertices have integer coordinates.

The first line of the input contains an integer $N$, the number of rectangles. Each of the next $N$ lines gives the coordinates of the lower-left corner and the upper-right corner of a rectangle.

Output a single positive integer, the perimeter of the union of all rectangles.

Constraints For all testdata, $1 \le N < 5000$, and all coordinate values are in the range $-10^4$ to $10^4$. Translated by ChatGPT 5