 Server Time: Sun Sep 27, 2020 4:40 pm
 Welcome ( logout ) E - Rectangle Union PDF (English) Ranklist
 Time Limit: 2 second(s) Memory Limit: 64 MB

Given some axis parallel rectangles, you have to find the union of their area. For example, see the shaded regions in the picture. Each rectangle will be denoted by four integers. They are x1, y1, x2, y2 where (x1, y1) denotes the lower left corner and (x2, y2) denotes the upper right corner. For the picture above, there are three rectangles. For the yellow rectangle the co-ordinates are (0, 2) and (3, 6). For the blue rectangle the co-ordinates are (1, 3) and (6, 7). For the green rectangle the co-ordinates are (2, 1) and (5, 4). So, the union area is (the shaded region) 31 square units.

# Input

Input starts with an integer T (≤ 13), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 30000). Each of the next n lines will contain four integers x1, y1, x2, y2 (0 ≤ x1, y1, x2, y2 ≤ 109, x1 < x2, y1 < y2) denoting a rectangle.

# Output

For each case, print the case number and the union area.

2

3

0 2 3 6

1 3 6 7

2 1 5 4

2

0 0 4 4

1 1 2 5

Case 1: 31

Case 2: 17

# Notes

Dataset is huge, use faster I/O methods.

Problem Setter: Jane Alam Jan
 Developed and Maintained by JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan