Tangency of Cuboids

题目描述

三维空间中有 $N$ 个长方体。 这些长方体两两不重叠。形式上，对于任意两个不同的长方体，它们的交集体积为 $0$。 第 $i$ 个长方体的对角线是连接两点 $(X_{i,1},Y_{i,1},Z_{i,1})$ 和 $(X_{i,2},Y_{i,2},Z_{i,2})$ 的线段，并且其棱都与坐标轴平行。 对于每个长方体，求与其相邻并共享一个面（face）的其他长方体的数量。
形式上，对于每个 $i$，求满足 $1\leq j \leq N$ 且 $j\neq i$ 且第 $i$ 个和第 $j$ 个长方体的表面交集具有正面积的 $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}$

输出格式

输出答案。

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
0
0

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

2
1
1

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

提示

$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$ 个和第 $2$ 个长方体共享一个对角为两点 $(0,0,1)$ 和 $(1,1,1)$ 的矩形。
第 $1$ 个和第 $3$ 个长方体共享一点 $(1,1,1)$，但不共享一个面。

标签: AtCoder|abc312E

来源

AtCoder|abc312E