Problem : 331 - 矩形交集

Problem Statistics

Solved Member: 26　　Submission: 69　　User Tried: 29

Statement:

在一個二維平面上有 n 個矩形，每個矩形的四條邊都和 x 軸平行或者是垂直。請你算出有多大的區域是被這 n 個矩形都覆蓋的呢？

Input:Output:

第一行有一個正整數 t，代表測試資料筆數。

每筆測試資料的第一行有一個正整數 n，代表矩形的個數。接下來 n 行每行有四個整數依序為 $x_1,y_1,x_2,y_2$，代表一個以 $(x_1,y_1)$ 和 $(x_2,y_2)$ 為對角的矩形。

$1 \le t \le 10$
$1 \le n \le 100$
$0 \le x_1 < x_2 \le 2 \times 10^9$
$0 \le y_1 < y_2 \le 2 \times 10^9$
其中 20% 的測試資料滿足： $n \le 2$

請輸出 t 行，每行一個數字，代表所有矩形相交的面積大小。若不存在所有矩形都相交的區域，請輸出 0。

Sample Input:Sample Output:

3
2
0 0 10 10
5 5 15 15
3
1 1 10 10
2 2 10 10
4 4 11 11
2
0 0 10 10
10 0 20 20

25
36
0

Source:

103附中資奧選拔賽

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	262144kb
1	500ms	262144kb	10
2	500ms	262144kb	10
3	500ms	262144kb	10
4	500ms	262144kb	10
5	500ms	262144kb	10
6	500ms	262144kb	10
7	500ms	262144kb	10
8	500ms	262144kb	10
9	500ms	262144kb	10
10	500ms	262144kb	10