← 返回题目列表

AtCoder · joi2013yo_e

E. 鱼类栖息地范围(鱼)

中文机器翻译题面 查看原题

配点: 100 点

問題

澳大利亚大陆以西是广阔的印度洋。海洋研究员 JOI 先生发现了一种生活在印度洋的物种。 N 我正在研究不同类型鱼的特性。

每种鱼类在海洋中都有一个长方体形状的栖息范围。鱼可以在其范围内的任何地方移动,包括边界,但它们永远不会离开其范围。海中的一点是3 实数 由 (x, y, d) 代表: (x, y, d) 是从天空看时从某个点向东的方向。 x ,向北 y 这是一个先进的位置,距离海面的深度是 代表点 d 。然而,假设海面是平坦的。

乔伊先生K 我想知道一种以上鱼类的栖息地范围有多少地方重叠。编写一个程序来查找这样一个地方的体积。 在


入力

输入是 由 1 + N 行组成。

1 行中,2 整数 N, K (1 \leqq K \leqq N \leqq 50)以空格作为分隔符。这是因为鱼 N 类型,K 表示您想要查找多种鱼类的栖息地范围重叠的区域的体积。

继续 N 行 i 行目 (1 \leqq i \leqq N)有6 整数 X_{i,1}, Y_{i,1}, D_{i,1}, X_{i,2}, Y_{i,2}, D_{i,2} (0 \leqq X_{i,1} < X_{i,2} \leqq 1\,000\,000 \ (= 10^6),0 \leqq Y_{i,1} < Y_{i,2} \leqq 1\,000\,000 \ (= 10^6),0 \leqq D_{i,1} < D_{i,2} \leqq 1\,000\,000 \ (= 10^6))被写入。这是i 每种鱼类的栖息地范围是 它表示一个以 8 点 (X_{i,1}, Y_{i,1}, D_{i,1}), (X_{i,2}, Y_{i,1}, D_{i,1}), (X_{i,2}, Y_{i,2}, D_{i,1}), (X_{i,1}, Y_{i,2}, D_{i,1}), (X_{i,1}, Y_{i,1}, D_{i,2}), (X_{i,2}, Y_{i,1}, D_{i,2}), (X_{i,2}, Y_{i,2}, D_{i,2}), (X_{i,1}, Y_{i,2}, D_{i,2}) 作为顶点的长方体。

出力

K 超过一种鱼类的栖息地范围重叠的整个区域的体积。 输出为 1 行。 例如,在


入力例 1

3 2
30 50 0 50 70 100
10 20 20 70 90 60
40 60 20 90 90 70

出力例 1

49000

入出力例 1 中,点 (45, 65, 65) 表示 1 鱼的类型和 3 这是一个满足条件的地方,因为它在某种鱼类的栖息范围内。另一方面,要点 (25, 35, 45) 表示 2 这不是一个满足条件的地方,因为它只是某些鱼类的栖息范围。鱼类的栖息范围如下图所示。点 O 代表海平面上的参考点。


入力例 2

1 1
0 0 0 1000000 1000000 1000000

出力例 2

1000000000000000000