Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Taken from IOI 1998.
Picture
A number of rectangular posters are pasted on
a wall (horizontal or vertical). Each
rectangle can be partially or totally covered by
the others.
Question:
Write a program to calculate the total perimeter.
An example with 7 rectangles is shown in Figure 1.
The corresponding boundary is the whole set
of line segments drawn in Figure 2.
Input specification
The first line of data contains the number of
rectangles on the wall. In each of the subsequent lines,
one can find the integer coordinates of the lower left
vertex and the upper right vertex of each rectangle.
The values of those coordinates are given as ordered
pairs consisting of an x-coordinate followed by
a y-coordinate. 0 ≤ number of rectangles < 5000
All coordinates are in the range [-10000,10000] and
any existing rectangle has a positive area.
Output specification
The output must contain a single line with a
non-negative integer which corresponds to the perimeter
for the input rectangles. The numeric value of
the result may need a 32-bit signed representation.
Sample Input I
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
|
Sample Output I
228
|
Для отправки решений необходимо выполнить вход.
|