Do Use Hexagon Grid 2

题目描述

我们有如下所示的无限六边形格子。 一个六边形格子用两个整数 $(i,j)$ 表示。
格子 $(i,j)$ 与以下六个格子相邻：

$(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$

输出格式

输出答案。

3 1
0 0
0 1
1 0

5

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

33

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

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)$ 两两互不相同。 输入中的所有数值都是整数。可能的选择集合有五种：$\{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\}$ 和 $\{(0,0),(1,0)\}$。

标签: AtCoder|abc280G

来源

AtCoder|abc280G