H - 三角形と格子点
解説
/
実行時間制限: 4 sec / メモリ制限: 256 MB
配点 : 1400 点
問題文
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 未満の整数である。
制約
- 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
入力
入力は以下の形式で標準入力から与えられる。
X_1 Y_1 X_2 Y_2 X_3 Y_3 W H
出力
答えを出力せよ。
入力例 1
0 0 4 1 2 3 2 1
出力例 1
32
下の図における f(A_iB_jC_k) (i, j, k \in \{1, 2\}) の和を 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 となります。
入力例 2
1 2 100 50 50 100 10 10
出力例 2
669378679
入力例 3
100 100 10000 1000 1000 10000 99 101
出力例 3
69068642
入力例 4
0 0 1000000000000 100000000000 100000000000 1000000000000 1 1
出力例 4
24258851
入力例 5
83014267509 107013567012 918384543326 586909285896 391608717054 614178832969 40000 40000
出力例 5
569338479