0138. Windows

Input file name:	widows.in
Output file name:	widows.out
Time limit:	1 s
Memory limit:	64 megabytes

n rectangular windows have appeared on the screen. Your task is to find the area covered simultaneously by all windows displayed.

Input file

The first line of the input file contains one integer number n (1 ≤ n ≤ 30000). The next n lines contain four integer numbers each: x₁ y₁ x₂ y₂, where (x₁, y₁) are coordinates of the upper-left corner of the window, and (x₂, y₂) are ones for the down-right. All coordinates do not exceed 5000 by an absolute value. Note that the y coordinates on the display grow downwards.

Output file

Write to the output file a single integer number – the area covered by all the windows displayed.

Examples:

widows.in	widows.out
2 0 0 3 2 1 1 4 4	2

Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version