Banner Home Page DIY Contests Problems Ranklist Status Statistics

覆盖的面积

Time Limit : 10000/5000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 0   Accepted Submission(s) : 0

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.


Input

输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.

注意:本题的输入数据较多,推荐使用scanf读入数据.

Output

对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.

Sample Input

2
5
1 1 4 2
1 3 3 7
2 1.5 5 4.5
3.5 1.25 7.5 4
6 3 10 7
3
0 0 1 1
1 0 2 1
2 0 3 1

Sample Output

7.63
0.00

Author

Ignatius.L & weigang Lee

Statistic | Submit | Back