AT_bitflyer2018_final_h 三角形と格子点

在 $xy$ 平面上，如果一个点 $P$ 的 $x$ 坐标和 $y$ 坐标都是整数，那么称 $P$ 为格子点。 对于平面上的一个三角形 $ABC$，定义函数 $f(ABC)$ 为位于三角形 $ABC$ 内部的格子点数目（不包括边界上的点）。 你会得到 $8$ 个整数：$X_1$, $Y_1$, $X_2$, $Y_2$, $X_3$, $Y_3$, $W$, $H$。你的任务是求出满足下面条件的所有三角形 $ABC$ 的 $f(ABC)$ 值的总和，并将其对 $10^9 + 7$ 取模。 条件如下： - 顶点 $A$ 的 $x$ 坐标在 $X_1$ 到 $X_1 + W - 1$ 之间，$y$ 坐标在 $Y_1$ 到 $Y_1 + H - 1$ 之间。 - 顶点 $B$ 的 $x$ 坐标在 $X_2$ 到 $X_2 + W - 1$ 之间，$y$ 坐标在 $Y_2$ 到 $Y_2 + H - 1$ 之间。 - 顶点 $C$ 的 $x$ 坐标在 $X_3$ 到 $X_3 + W - 1$ 之间，$y$ 坐标在 $Y_3$ 到 $Y_3 + H - 1$ 之间。

输入如下： > $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ X_3 $ $ Y_3 $ $ W $ $ H $

输出计算结果，记得对 $10^9 + 7$ 取模。

- 坐标 $X_i, Y_i$ 满足 $0 \leq X_i, Y_i \leq 10^{12}$，其中 $1 \leq i \leq 3$。 - 宽度和高度 $W, H$ 满足 $1 \leq W, H \leq 40\,000$。 - 坐标关系：$X_1 + W \leq X_3$，$X_3 + W \leq X_2$，$Y_1 + H \leq Y_2$，$Y_2 + H \leq Y_3$。 ### 示例解释 下图展示了若干三角形 $A_iB_jC_k$ 的 $f$ 值，它们的和需被 $10^9 + 7$ 模： - $f(A_1B_1C_1) = 4$ - $f(A_1B_1C_2) = 3$ - $f(A_1B_2C_1) = 6$ - $f(A_1B_2C_2) = 4$ - $f(A_2B_1C_1) = 3$ - $f(A_2B_1C_2) = 3$ - $f(A_2B_2C_1) = 5$ - $f(A_2B_2C_2) = 4$ 答案就是以上这些数的总和，再对 $10^9 + 7$ 取模，结果为 $32$。 **本翻译由 AI 自动生成**