← 返回题目列表

AtCoder · abc312_e

H. 长方体的相切

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

分数: 500 点

问题陈述

有 N 三维空间中的长方体。

这些长方体不重叠。 形式上,对于其中任意两个不同的长方体,它们的交集的体积为 0.

的对角线 i第一个长方体是连接两个点的线段 (X_{i,1},Y_{i,1},Z_{i,1}) 和 (X_{i,2},Y_{i,2},Z_{i,2}),其边缘均平行于其中一个坐标轴。

对于每个长方体,找到与其共享一个面的其他长方体的数量。
正式地,对于每个 i,查找数量 j 与 1\leq j \leq N 和 j\neq i 使得表面的交集 i-th 和 j第一个长方体的面积为正。

约束

  • 1 \leq N \leq 10^5
  • 0 \leq X_{i,1} < X_{i,2} \leq 100
  • 0 \leq Y_{i,1} < Y_{i,2} \leq 100
  • 0 \leq Z_{i,1} < Z_{i,2} \leq 100
  • 长方体与正体积没有交集。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
X_{1,1} Y_{1,1} Z_{1,1} X_{1,2} Y_{1,2} Z_{1,2}
\vdots
X_{N,1} Y_{N,1} Z_{N,1} X_{N,2} Y_{N,2} Z_{N,2}

输出

打印答案。


示例输入 1

4
0 0 0 1 1 1
0 0 1 1 1 2
1 1 1 2 2 2
3 3 3 4 4 4

示例输出 1

1
1
0
0

的 1-st 和 2-nd 长方体共享一个矩形,其对角线是连接两点的线段 (0,0,1) 和 (1,1,1).
的 1-st 和 3-rd 长方体共享一个点 (1,1,1),但不共享表面。


示例输入 2

3
0 0 10 10 10 20
3 4 1 15 6 10
0 9 6 1 20 10

示例输出 2

2
1
1

示例输入 3

8
0 0 0 1 1 1
0 0 1 1 1 2
0 1 0 1 2 1
0 1 1 1 2 2
1 0 0 2 1 1
1 0 1 2 1 2
1 1 0 2 2 1
1 1 1 2 2 2

示例输出 3

3
3
3
3
3
3
3
3