AT_abc312_e [ABC312E] Tangency of Cuboids

题目描述

在三维空间中有 $N$ 个长方体。

这些长方体之间没有重叠。严格来说，任意两个不同的长方体的公共部分体积为 $0$。

第 $i$ 个长方体由两点 $(X_{i,1}, Y_{i,1}, Z_{i,1})$ 和 $(X_{i,2}, Y_{i,2}, Z_{i,2})$ 的连线作为对角线，且所有边都平行于某一坐标轴。

请对于每个长方体，求出它与多少个其他长方体通过面相接。
更严格地说，对于每个 $i$，求满足 $1 \leq j \leq N$ 且 $j \neq i$ 的 $j$ 中，有多少个 $j$ 使得第 $i$ 个长方体的表面与第 $j$ 个长方体的表面有正面积的公共部分。

输入格式

输入以如下格式从标准输入读入。

$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

输入 #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

输入输出样例 #2

输入 #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

输入 #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

说明/提示

限制条件

• $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$
• 任意两个长方体没有正体积的公共部分
• 所有输入均为整数

样例解释 1

第 $1$ 个长方体和第 $2$ 个长方体共用以 $(0,0,1)$ 和 $(1,1,1)$ 为对角线的矩形面。第 $1$ 个长方体和第 $3$ 个长方体仅在点 $(1,1,1)$ 处相交，但没有通过面相接。

由 ChatGPT 4.1 翻译