← 返回题目列表

AtCoder · icpc2015summer_day4_g

G. 立方体的表面积

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

问题陈述

太郎喜欢单人游戏”Surface Area of Cubes".

在这个游戏中,他最初有一个由 $A \times B \times C$ 个单位立方体(都是 1 x 1 x 1 立方体)组成的 $A \times B \times C$ 长方体。每个单位立方体的中心放置在 3 维坐标 $(x,y,z)$ 处,其中 $x,y,z$ 均为整数 $(0\leq x\leq A-1, 0\leq y\leq B-1, 0\leq z\leq C-1)$。然后,游戏大师从长方体中移除 $N$ 个不同的单位立方体。当$N$个立方体被移除后,他必须精确地说出该物体的总表面积才能赢得比赛。

请注意,删除操作不会更改未删除的立方体的位置。 而且,不仅可以去除长方体表面的立方体,还可以去除内部的立方体。此外,通过移除立方体,可以将物体分成多个部分。请注意,该游戏的玩家还必须计算从外部无法到达的表面积。

太郎知道有多少个方块被移走了,但是这个游戏对他来说很难,所以他想通过作弊来赢得这个游戏!你是太郎的朋友,你的工作是编写一个程序,当给定长方体的大小和移除的立方体的坐标时,代表太郎计算物体的总表面积。


输入

输入的格式如下。

测试用例的第一行包含四个整数 $A,B,C$ 和 $N (1\leq A,B,C\leq 10^8,0\leq N\leq \min \{1{,}000, A\times B\times C-1 \} )。$

接下来的 $N$ 行中的每一行都包含非负整数 $x、y$ 和 $z$,它们表示删除的立方体的坐标。您可以假设这些坐标是不同的。

输出

输出移除了 $N$ 立方体的物体的总表面积。


示例输入 1

2 2 2 1
0 0 0

样本输入 1 的输出

24

示例输入 2

1 1 5 2
0 0 1
0 0 3

样本输入 2 的输出

18

示例输入 3

3 3 3 1
1 1 1

样本输入 3 的输出

60