AT_abc280_g [ABC280G] Do Use Hexagon Grid 2

题目描述

有一个如下所示的无限大的六边形网格。

六边形的格子可以用两个整数 $i,j$ 表示为 $(i,j)$。
格子 $(i,j)$ 与以下 $6$ 个格子通过边相邻：

• $(i-1,j-1)$
• $(i-1,j)$
• $(i,j-1)$
• $(i,j+1)$
• $(i+1,j)$
• $(i+1,j+1)$

定义两个格子 $X,Y$ 之间的距离为：从格子 $X$ 沿着相邻的格子移动到格子 $Y$ 所需的最小移动次数。
例如，格子 $(0,0)$ 与格子 $(1,1)$ 的距离是 $1$，格子 $(2,1)$ 与格子 $(-1,-1)$ 的距离是 $3$。

现在给定 $N$ 个格子 $(X_1,Y_1),\ldots,(X_N,Y_N)$。
从这 $N$ 个格子中选择至少一个格子的方案中，要求所选的任意两个格子的距离都不超过 $D$。请问有多少种不同的选择方法？
请输出答案对 $998244353$ 取模的结果。

输入格式

输入以如下格式从标准输入读入。

$N$ $D$
$X_1$ $Y_1$
$\vdots$
$X_N$ $Y_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 1
0 0
0 1
1 0

输出 #1

5

输入输出样例 #2

输入 #2

9 1
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

输出 #2

33

输入输出样例 #3

输入 #3

5 10000000000
314159265 358979323
846264338 -327950288
-419716939 937510582
-97494459 -230781640
628620899 862803482

输出 #3

31

说明/提示

限制条件

• $1\leq N\leq 300$
• $-10^9\leq X_i,Y_i\leq 10^9$
• $1\leq D\leq 10^{10}$
• $(X_i,Y_i)$ 互不相同
• 输入均为整数

样例解释 1

可以选择的格子集合有 $\{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\},\{(0,0),(1,0)\}$ 共 $5$ 种。

由 ChatGPT 4.1 翻译