AT_bitflyer2018_final_h 三角形と格子点

[problemUrl]: https://atcoder.jp/contests/bitflyer2018-final/tasks/bitflyer2018_final_h $ xy $ 平面上の点 $ P $ が格子点であるとは、点 $ P $ の $ x $ 座標および $ y $ 座標がともに整数であることをいいます。 $ xy $ 平面上の三角形 $ 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 $ 未満の整数であり、$ y $ 座標は $ Y_1 $ 以上 $ Y_1\ +\ H $ 未満の整数である。 - 頂点 $ B $ の $ x $ 座標は $ X_2 $ 以上 $ X_2\ +\ W $ 未満の整数であり、$ y $ 座標は $ Y_2 $ 以上 $ Y_2\ +\ H $ 未満の整数である。 - 頂点 $ C $ の $ x $ 座標は $ X_3 $ 以上 $ X_3\ +\ W $ 未満の整数であり、$ y $ 座標は $ Y_3 $ 以上 $ Y_3\ +\ H $ 未満の整数である。

入力は以下の形式で標準入力から与えられる。 > $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ X_3 $ $ Y_3 $ $ W $ $ H $

答えを出力せよ。

### 制約 - $ 0\ \leq\ X_i,\ Y_i\ \leq\ 10^{12} $ ($ 1\ \leq\ i\ \leq\ 3 $) - $ 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 $ ### Sample Explanation 1 下の図における $ f(A_iB_jC_k) $ ($ i,\ j,\ k\ \in\ \{1,\ 2\} $) の和を $ 10^9\ +\ 7 $ で割ったあまりを求めれば良いことになります。 !\[image for sample 1\](https://img.atcoder.jp/bitflyer2018-final/ae5840b0cc630e284a22c89b18a98a5f.png) - $ 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 $ となります。