#P2058. C15_2*【扫描线】亚特兰蒂斯[POJ1151]

C15_2*【扫描线】亚特兰蒂斯[POJ1151]

Description

0x40数据结构进阶(0x43 线段树)例题4:亚特兰蒂斯

【题意】

nn 个矩形的面积并(矩形的四边平行于坐标轴)。

【输入格式】

输入包含多组测试用例。

每组数据:

第一行一个正整数 nn0n1000≤n≤100)。

接下来 nn 行每行四个实数 x1,y1,x2,y2x_1, y_1, x_2, y_20x1<x2105,0y1<y21050≤ x_1< x_2≤10^5,0≤ y_1 < y_2≤10^5),(x1,y1)(x_1,y_1)(x2,y2)(x_2,y_2) 分别是矩形的左下角位置和右上角位置。

当输入样例 n=0n=0 时,表示输入终止,该样例无需处理。

【输出格式】

每组测试用例输出两行。

第一行输出 Test case #k,其中k是测试样例的编号,从 1 开始。

第二行输出 Total explored area: a ,其中 a 是总地图面积(即此测试样例中所有矩形的面积并,注意如果一片区域被多个地图包含,则在计算总面积时只计算一次),精确到小数点后两位数。 在每个测试用例后输出一个空行。

【输入样例】

2
10 10 20 20
15 15 25 25.5
0

【输出样例】

Test case #1
Total explored area: 180.00