|
F |
Avoiding
Overlaps Input: Standard Input Output: Standard Output |
|
Given N regular rectangles in a sequence. Following this sequence you have to draw every rectangles if it does not overlap with any rectangle which has been drawn already. Calculate the total area of drawn rectangles.
Note: A rectangle is regular if and only if it’s sides are all parallel to the axis.
Input
The first line of the input
contains the number of test cases T (1 ≤ T ≤ 100). Each case starts with a single line
containing N(0 ≤ N ≤ 10000), the number of rectangles in the
sequence. Next N lines will represent the sequence of rectangles. Each of the
next N lines will represent one rectangle having four integers x1, y1, x2, y2
(-100 < x1, y1, x2, y2 < 100, x1<x2, y1<y2), here (x1, y1) is the
lower left corner of the rectangle and (x2, y2) is the upper right corner of
the rectangle.
Output
For each test case, print the case number and a single integer, the total area covered by rectangles you drew.
Sample Input Output for
Sample Input
|
1 3 -1 -1 1 1 0 0 10 10 1 0 2 2 |
Case 1: 6 |
Warning:
The size of input file is around 12 MB.
Problemsetter:
Special Thanks: Sohel Hafiz