8281: ABC280 —— G - Do Use Hexagon Grid 2
[Creator : ]
Description
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:
For example, the distance between cells (0,0) and (1,1) is 11, and the distance between cells (2,1) and (−1,−1) is 3.
You are given N cells $(X_1,Y_1),…,(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.
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)
For example, the distance between cells (0,0) and (1,1) is 11, and the distance between cells (2,1) and (−1,−1) is 3.
You are given N cells $(X_1,Y_1),…,(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.
Input
The input is given from Standard Input in the following format:
$N\ D$
$X_1\ Y_1$
$⋮$
$X_N\ Y_N$
$N\ D$
$X_1\ Y_1$
$⋮$
$X_N\ Y_N$
Output
Print the answer.
Constraints
$1≤N≤300$
$−10^9≤X_i,Y_i≤10^9$
$1≤D≤10^{10}$
$(X_i,Y_i)$ are pairwise distinct.
All values in the input are integers.
$−10^9≤X_i,Y_i≤10^9$
$1≤D≤10^{10}$
$(X_i,Y_i)$ are pairwise distinct.
All values in the input are integers.
Sample 1 Input
3 1
0 0
0 1
1 0
Sample 1 Output
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 2 Input
9 1
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
Sample 2 Output
33
Sample 3 Input
5 10000000000
314159265 358979323
846264338 -327950288
-419716939 937510582
-97494459 -230781640
628620899 862803482
Sample 3 Output
31