格子点を数えるパートはもっと高速になります。

• \(3\) 次元凸包を半空間の積として求め、整数であるような \(z\) 座標で切って半平面の積にします。切る位置は \(O(M)\) 個あります。
• 半平面の積によって作られる凸多角形を求めます。半空間の積の状態であらかじめソートしておけば \(O(N)\) で求められます。
• 凸多角形を整数であるような \(y\) 座標で切って区間にします。切る位置は \(O(M)\) 個あります。
• 区間に含まれる格子点の数は \(O(1)\) で求められます。

したがって、格子点を数えるパートは \(O(M(N + M))\) になります。

実装例 (C++)
( \(2\) 倍, \(3\) 倍した場合の格子点の数を求めていますが、非常に高速です)
( \(N\) 点が同一平面上にある場合も解いています)

また、凸多角形に含まれる格子点の数は Sum of Floor of Linear を用いて \(O(N \log M)\) で求めることができるので、\(O(NM \log M)\) にすることもできます。