2212: Fences

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]


You own an island. Everyday, when the tide rises, the island is flooded by sea water. After much thinking,
you decided to set up a farm by horizontal and vertical fence strips of different lengths and heights. Two
fences can intersect in at most one point, not necessarily at their ends.
Given the height the tide will reach and the positions and heights of all fence strips, your task is to
calculate the total area of land which will not be flooded during the high tide.


The ¯rst line contains t (1<=t<=10), the number of test cases followed. The ¯rst line of a
test case contains an integer n indicating the number of fence strips in the island (1 · n · 200).
Each of the next n lines contains ¯ve integers x1, y1, x2, y2, h(x1 = x2 or y1 = y2, but not both;
-100<=x1; y1; x2; y2<=100; 1<=h<=100), representing respectively the start point of the strip (x1,y1),
the end point of the strip (x2; y2) and the strip height h. The last line contains an integer w(1<=w<=100)
representing the tide height. Coordinates are given in meters, heights in centimeters.


For each test case, print one line of output, containing an integer, the total area (in m2) of the land which
will not be flooded.

Sample Input Copy

-20 20 20 20 20
20 20 20 -20 20
0 0 0 20 10
-10 0 20 0 20
-20 20 20 20 20
20 20 20 -20 20
0 0 0 20 10
-10 0 20 0 20

Sample Output Copy