102806: [AtCoder]ABC280 G - Do Use Hexagon Grid 2

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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

Input

题意翻译

给定正六边形网格：格子 $(x,y)$ 与 $(x-1,y),(x+1,y),(x,y-1),(x,y+1),(x+1,y+1),(x-1,y-1)$ 紧邻。 现在给定你网格中若干个格子 $(X_i,Y_i)$，请你求出，选择若干个格子，其中两两距离不超过给定值 $D$ 的方案数。两种方案不同当且仅当存在一个格子在一个方案中出现而在另一个方案中未出现。 答案对 $998244353$ 取模。 其中两个格子的距离：一个格子可以花费 $1$ 代价到达与其紧邻的一个格子，两个格子间距离的定义为在所有起点为其中一个格子，终点为另一个格子的路径中，花费总和的最小值。 数据范围：$1\leqslant N\leqslant 300,|X_i|,|Y_i|\leqslant 10^9,1\leqslant |D|\leqslant 10^{10}$

Output

分数：$600$分

问题描述

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

一个六边形格子用两个整数$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$取模的结果。

约束条件

  • $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)\}$。

样例输入 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

Source/Category

加入题单

算法标签：