Score : $600$ points

问题描述

我们有一个无限的六边形网格，如下图所示。

一个六边形格子用两个整数 $i$ 和 $j$ 表示为 $(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$ 取模的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have an infinite hexagonal grid shown below.

A hexagonal cell is represented as $(i,j)$ with two integers $i$ and $j$.
Cell $(i,j)$ is adjacent to the following six cells:

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

Let us define the distance between two cells $X$ and $Y$ by the minimum number of moves required to travel from cell $X$ to cell $Y$ by repeatedly moving to an adjacent cell.
For example, the distance between cells $(0,0)$ and $(1,1)$ is $1$, and the distance between cells $(2,1)$ and $(-1,-1)$ is $3$.

You are given $N$ cells $(X_1,Y_1),\ldots,(X_N,Y_N)$.
How many ways are there to choose one or more from these $N$ cells so that the distance between any two of the chosen cells is at most $D$?
Find the count modulo $998244353$.

Constraints

• $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)$ are pairwise distinct.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $D$

$X_1$ $Y_1$

$\vdots$

$X_N$ $Y_N$

Output

Print the answer.

Sample Input 1

3 1
0 0
0 1
1 0

Sample Output 1

5

There are five possible sets of the chosen cells: $\{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\}$, and $\{(0,0),(1,0)\}$.

Sample Input 2

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

Sample Output 2

33

Sample Input 3

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

Sample Output 3

31

update @ 2024/3/10 11:47:03