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 x_{1}, y_{1}, x_{2}, y_{2} where (x_{1}, y_{1}) denotes the lower left corner and (x_{2}, y_{2}) 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 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 x_{1}, y_{1}, x_{2}, y_{2} (0 ≤ x_{1}, y_{1}, x_{2}, y_{2} ≤ 10^{9}, x_{1} < x_{2}, y_{1} < y_{2}) denoting a rectangle.
For each case, print the case number and the union area.
Sample Input |
Output for Sample Input |
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 |
Dataset is huge, use faster I/O methods.
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |