G - Do Use Hexagon Grid 2 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

以下のような、無限に広い六角形のグリッドがあります。

六角形のマスは 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)

2 つのマス 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 マスの中から 1 つ以上のマスを選ぶ方法のうち、選んだマスのうちどの 2 マスの距離も D 以下になるようなものは何通りありますか？
998244353 で割ったあまりを求めてください。

制約

  • 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) は相異なる
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N D
X_1 Y_1
\vdots
X_N Y_N

出力

答えを出力せよ。

入力例 1

3 1
0 0
0 1
1 0

出力例 1

5

選ぶマスの集合として考えられるのは \{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\},\{(0,0),(1,0)\} の 5 通りです。

入力例 2

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

出力例 2

33

入力例 3

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

出力例 3

31

Score : 600 points

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