Preparing NOJ

自由堆叠的屋顶

1000ms 65536K

Description:

sed 同学最近突发奇想,认为伟大的建筑物的屋顶应该是“自由堆叠”出来的,他的设计方案是:将各种颜色的长方形建筑板材堆叠在一起,并保证各个板材长边、宽边均相互平行或在一条直线上,板材之间的重叠部分用连接装置固定在一起。

你的任务是计算这个“自由堆叠的屋顶”所覆盖的面积。sed 将会在屋顶平面上建立一个二维坐标系,提供给你每个长方形建筑板材左上角、右下角的坐标。为简化计算,这里忽略板材的厚度,假设它们都在同一个平面上。

Input:

输入数据包含多组测试案例。

每组测试案例由N0N100)开头,后续N行每行包含4个实数x1;y1;x2;y2 (0 <= x1 < x2 <= 100000建筑单位;0 <= y1 < y2 <= 100000建筑单位)

(x1; y1) (x2;y2)分别是长方形建筑板材左上角、右下角的坐标。

单独一个行输入0表示输入结束,无需处理。

Output:

对于每个测试用例,输出以下信息: 1行形如“Build #k”,这里k是测试用例序号(以1开始),第二行形如“Total area: a”,a是总覆盖面积,保留两位小数。

Sample Input:

2
10 10 20 20
15 15 25 25.5
1
10 10 20 20
0

Sample Output:

Build #1
Total explored area: 180.00
Build #2
Total explored area: 100.00

Note:

本题由旧版NOJ导入,来源:南京邮电大学计算机学院首届ACM程序设计大赛(2009)

Info

NOJ

Provider NOJ

Code NOJ1036

Tags

Submitted 4

Passed 2

AC Rate 50%

Date 04/20/2019 10:03:10

Related

Nothing Yet