#P18566. [ukiepc2026]Bust Blasting

[ukiepc2026]Bust Blasting

Bust Blasting

题目描述

查理是一位数控加工师,打算复制一尊由体素构成的游戏角色雕像。他拍摄了雕像的三个方向的照片,并将每张照片的轮廓描绘为一个边均平行于坐标轴的简单多边形(可以是凹多边形):

  • 正视图:在 xyxy 平面上的投影;
  • 侧视图:在 zyzy 平面上的投影(注意坐标顺序为 z,yz,y);
  • 俯视图:在 xzxz 平面上的投影。

对于空间中的任意一点 (x,y,z)(x,y,z),只有当它在上述三个平面上的投影 (x,y)(x,y)、(z,y)(z,y)、(x,z)(x,z) 全部位于对应多边形内或边界上时,这一点才会保留下来;否则将被切除。

切削后得到的三维形状可能是不连通的,也可能为空。

请计算最后保留的形状的总体积,单位为立方厘米。

图示(重绘示意图)

图 B.1:正视、侧视和俯视的三个轮廓,示意三个正交投影共同确定三维形状。

图 B.1:正视、侧视和俯视的三个轮廓,示意三个正交投影共同确定三维形状。 本图为重绘示意图。

输入格式

输入依次给出三个视图的多边形,顺序为正视图、侧视图、俯视图。每个视图包含:

  • 一个整数 nin_i,表示该多边形的顶点数;
  • 随后的 nin_i 对整数 uij,viju_{ij},v_{ij},按逆时针顺序给出顶点坐标。

同一个视图的顶点数量和所有顶点坐标可以写在同一行。输入中的空白符均可作为分隔。

输出格式

输出一个整数,表示最终形状的总体积(立方厘米)。

样例 #1

输入

4 0 0 10 0 10 10 0 10
4 5 7 15 7 15 15 5 15
4 11 6 11 12 6 12 6 6

输出

72

数据范围与保证

  • 对于三个视图分别有 4≤ni≤1004\le n_i\le100;
  • 所有顶点坐标均为整数,且 −10000≤uij,vij≤10000-10000\le u_{ij},v_{ij}\le10000;
  • 每条边均平行于该平面的某条坐标轴,即相邻顶点的两个坐标中至少有一个相等;
  • 不存在连续三个共线的顶点;
  • 每个视图所给轮廓都是简单多边形,顶点按逆时针排列。