little-deepak-and-game-of-thrones

Little Deepak is the most popular cartographer in the entire realm of Game of Thrones. But, he has a simple problem: he's an alcohol addict. And no, that's not meant in a good way, to say the least.

Since, the world of Game of Thrones has too many kingdoms, lands, territories, rivalries and what not - so every other king has a different idea of what land they "own!" And because of this uncertainty, there are many areas which are present in the maps of many kings, confusing the serious contenders for the Iron Throne in planning, and plotting their revenge, murder and what not!

Now, little Deepak is high almost all the time, he draws a lot of maps having similar places attributed to different kings - but, anyhow, all of these drunk map designs can be used to give a complete picture of all the kingdoms competing for the Iron Throne!

A map is always rectangular in shape, having length and breadth. Let's say that one unit on this map is equivalent to one unit on actual ground, can you help Little Deepak in determining the total area of the ground he has drawn using his maps? Obviously, certain regions are going to appear in multiple maps but they should only be considered once.

PS: A cartographer is someone who makes maps, by the way!

Input format:
The first line contains an integer, tc, denoting the number of test cases. After that, one line with an integer m, denoting the number of maps. m lines with four integers. The first two integers, x1, y1, will be depicting the coordinates of bottom-left (SW) corner, the next two integers, x2, y2, will be depicting the coordinates of the top-right (NE) corner. 

Output format:
The total area covered in all the maps.

Constraints:
1 ≤ t ≤ 100
1 ≤ m ≤ 1300
0 ≤ x1, x2 ≤10^6
0 ≤ y1, y2 ≤10^6
x1 < x2
y1 < y2

The shape of the map is a rectangle.

SAMPLE INPUT
1
2
0 0 13 13
10 4 14 8

SAMPLE OUTPUT
173

Source: hackerearth | Difficulty: MEDIUM
Tags: Geometry

Sweep line algorithms

Mathematics


Solutions: