MAIN8_B - Overlapping Squares
You are given N (1<=N<=20000) squares on X-Y plane. Your task is to find the area which is common to all the squares (Area of intersection of all the squares)
Input
The first line contains T, the number of test cases. Then T test cases follow. First line of each test case contains N, the number of squares. Each of following N lines contain 3 integer (X, Y, L) coordinate of lower left vertex and size of the square.
-10^9<=X,Y<=10^9 1<=L<=10^9
Output
For each test case print the answer in a new line.
Example
Input: 2 2 0 0 10 1 1 11 2 10 10 25 1 1 3 Output: 81 0
Added by: | Mahesh Chandra Sharma |
Date: | 2011-04-20 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own problem used for NSIT-IIITA Main contest #8 |