[NOI1997]卫星覆盖

成绩 0 开启时间 2013年01月22日 星期二 11:45
折扣 0.8 折扣时间 2013年01月22日 星期二 11:45
允许迟交 关闭时间 2013年01月22日 星期二 11:45
输入文件 satellitecover.in 输出文件 satellitecover.out

SERCOI(Space-Earth Resource Cover-Observe lnstitute)是一个致力于利用卫星技术对空间和地球资源进行覆盖观测的组织。现在他们研制成功一种新型资源观测卫星-SERCOI-308。这种 卫星可以覆盖空间直角坐标系中一定大小的立方体空间,卫星处于该立方体的中心。

其中(x,y,z)为立方体的中心点坐标,r为此中心点到立方体各个面的距离(即r为立方体高的一半).立方体的各条边均平行于相应的坐标轴。我们可以用一个四元组(x,y,z,r)描述一颗卫星的状态,它所能覆盖的空间体积 。 由于一颗卫星所能覆盖的空间体积是有限的,因此空间中可能有若干颗卫星协同工作。它们所覆盖的空间区域可能有重叠的地方,如下图所示(阴影部分表示重叠的区域)。

Image:Satellitecover.png

写一个程序,根据给定的卫星分布情况,计算它们所覆盖的总体积。

输入输出

输入文件的第一行是一个正整数N(1<=N<=100):表示空间中的卫星总数。接下来的N行每行给 出了一颗卫星的状态,用空格隔开的四个正整数x,y,z,r依次表示了该卫星所能覆盖的立方体空间的中心点坐标和半高,其中 -1000<=x,y,z<=1000, 1<=r<=200。

输出文件只有一行,包括一个正整数,表示所有这些卫星所覆盖的空间总体积。

样例

输入文件

3
0 0 0 3
1 -1 0 1
19 3 5 6

输出文件

1944