Expanded Hull
题目描述
给定整数 N,K,以及三维空间中的 N 个点
(X1,Y1,Z1),…,(XN,YN,ZN)。
将每个点的三个坐标都乘以 K,得到
(KX1,KY1,KZ1),…,(KXN,KYN,KZN)。
设这些新点的凸包为 V。请计算位于 V 的内部或边界上、且三个坐标均为整数的点的数量,对 998244353 取模。
输入格式
N K
X_1 Y_1 Z_1
...
X_N Y_N Z_N
输入仅包含一组数据,所有数均为整数。
输出格式
输出一个整数,表示所求点数对 998244353 取模后的结果。
数据范围
- 4≤N≤100。
- 1≤K≤1015。
- −200≤Xi,Yi,Zi≤200。
- 给出的 N 个点两两不同。
- 不存在一个平面经过所有给出的点,即这些点不全共面。
样例输入 1
4 2
0 0 0
1 0 0
0 1 0
0 0 1
样例输出 1
10
样例输入 2
4 10000
0 0 0
1 0 0
0 1 0
0 0 1
样例输出 2
59878050
样例输入 3
8 314159265358979
5 -3 -3
-5 -3 -3
0 5 -3
0 0 10
4 2 6
-4 2 6
0 -5 6
0 0 -5
样例输出 3
152811018
样例说明
第一组样例中,满足条件的10个整数点为
(0,0,0)、(1,0,0)、(2,0,0)、(0,1,0)、(1,1,0)、
(0,2,0)、(0,0,1)、(1,0,1)、(0,1,1)、(0,0,2)。