TopCoder

User's AC Ratio

91.3% (63/69)

Submission's AC Ratio

29.7% (132/445)

Description

給你很多平面上的矩形,請求出它們覆蓋的總表面積。

Input Format

輸入檔只包含一筆測試資料。
第一列有一個正整數n(1<=n<=100,000),代表有n個矩形。
接下來有n列,每列有四個整數 L,R,D,U(0<=L<R<=1,000,000;0<=D<U<=1,000,000)代表矩形的左、右、下、上四個邊界座標。

Output Format

請輸出覆蓋的總面積。

Sample Input

2
1 10 1 10
0 2 0 2

Sample Output

84

Hints

Problem Source

原TIOJ1224 / TIOJ 2008例行賽03-Elite (prob F)。經典問題練習。Problem Setter:Tmt, kelvin。

Subtasks

For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 5
For Testdata: 17 ~ 17, Score: 15
No. Time Limit (ms) Memory Limit (KiB)
0 1900 65536
1 1900 65536
2 1900 65536
3 1900 65536
4 1900 65536
5 1900 65536
6 1900 65536
7 1900 65536
8 1900 65536
9 1900 65536
10 1900 65536
11 1900 65536
12 1900 65536
13 1900 65536
14 1900 65536
15 1900 65536
16 1900 65536
17 1900 65536