5482 - Balloons in a Box

通过次数

0

提交次数

0

时间限制 : 1 秒
内存限制 : 256 MB

  你要写一个程序,使得能够模拟在长方体的盒子里放置球形的气球。
  接下来是模拟的方案。假设你已知一个长方体的盒子和一个点集。每一个点代表一个可以放置气球的位置。在一个点上放置一个气球,就是以这个点为球心,然后让这个球膨胀,直到触及盒子的边缘或者一个之前已经被放置好的气球。你不能使用一个在盒子外面或者在一个之前已经放置好的气球里面的点。但是,你可以按你喜欢的任意顺序使用这些点,而且你不需要每个点都用。你的目标是按照某种顺序在盒子里放置气球,使得气球占据的总体积最大。
  你要做的是计算盒子里没被气球占据的体积。

输入

  第一行包含一个整数n表示集合里点的个数(1≤n≤6)。第二行包含三个整数表示盒子的一个角落的(x,y,z)坐标,第三行包含与之相对的那个角落的(x,y,z)坐标。接下来n行,每行包含三个整数,表示集合中每个点的(x,y,z)坐标。这个盒子的每维的长度都是非零的,而且它的边与坐标轴平行。

输出

  只有一行,为那个盒子没被气球占据的最小体积(四舍五入到整数)。

样例

输入

2
0 0 0
10 10 10
3 3 3
7 7 7

输出

774

提示

数据规模和约定

所有坐标的绝对值小于等于1000
对于20%的数据:n=1
对于50%的数据:1≤n≤3
对于100%的数据:1≤n≤6

来源

蓝桥杯训练