问题 4346 --(2008珠海赛) Fences

4346: (2008珠海赛) Fences

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

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 first line contains t (1 ≤ t ≤ 10), the number of test cases followed. The first 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 five 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 m^2) of the land which will not be flooded.

样例输入

2
4
-20 20 20 20 20
20 20 20 -20 20
0 0 0 20 10
-10 0 20 0 20
10
4
-20 20 20 20 20
20 20 20 -20 20
0 0 0 20 10
-10 0 20 0 20
11

样例输出

400
0

来源

[提交][状态]