AT_ttpc2022_n.Expanded Hull

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个整数 $K$ 和 $3$ 维空间中的 $N$ 个点 $(x_1, y_1, z_1), \dots, (x_N, y_N, z_N)$ 。

请你求出在 $N$ 个点 $(K x_1, K y_1, K z_1), \dots, (K x_N, K y_N, K z_N)$ 构成的凸包的内部或表面上的所有整数坐标点的个数，并将结果对 $998244353$ 取模输出。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$
$x_1$ $y_1$ $z_1$
$\vdots$
$x_N$ $y_N$ $z_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

说明/提示

样例解释 1

$4$ 个点 $(0,0,0),(2,0,0),(0,2,0),(0,0,2)$ 的凸包的内部和表面上所包含的所有整数坐标点为： $(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)$ ，共 $10$ 个。

样例解释 2

$4$ 个点 $(0,0,0),(10000,0,0),(0,10000,0),(0,0,10000)$ 的凸包内所包含的所有整数坐标点有 $166\,766\,685\,001$ 个，因此答案是其对 $998244353$ 取模后的 $59878050$ 。

数据范围与说明

输入均为整数。
$4 \leq N \leq 100$
$1 \leq K \leq 10^{15}$
$-2 \times 10^2 \leq x_i, y_i, z_i \leq 2 \times 10^2\ (1 \leq i \leq N)$
对任意 $i < j$ ，有 $(x_i, y_i, z_i) \neq (x_j, y_j, z_j)$ 。
不存在经过所有 $N$ 个点的平面。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页