Scalene Triangle Area

题目描述

我们有一个 $N \times N$ 的网格。 从上往下第 $i$ 行、从左往右第 $j$ 列的格子称为 $(i,j)$。
每个格子最多有一枚棋子。
网格的状态由 $N$ 个字符串 $S_i$ 给出：

如果 $S_i$ 的第 $j$ 个字符是 $O$，则 $(i,j)$ 上有一枚棋子； 如果 $S_i$ 的第 $j$ 个字符是 $X$，则 $(i,j)$ 上没有棋子。

给定一个整数 $M$。 使用该 $M$，我们定义放在 $(s,t)$ 的棋子 $P$ 覆盖格子 $(u,v)$ 当且仅当满足所有下列条件：

$s \le u \le N$ $t \le v \le N$ (u - s) + \frac{(v - t)}{2} < M

对于每个 $Q$ 个格子 $(X_i,Y_i)$，求有多少枚棋子覆盖该格子。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $S_1$ $S_2$ $\vdots$ $S_N$ $Q$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_Q$ $Y_Q$

输出格式

输出 $Q$ 行。
第 $i$ 行（ $1 \le i \le Q$ ）应当包含覆盖 $(X_i,Y_i)$ 的棋子数，作为整数。

4 2
OXXX
XXXX
XXXX
XXXX
6
1 1
1 4
2 2
2 3
3 1
4 4

1
1
1
0
0
0

####
##..
....
....

5 10
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
5
1 1
2 3
3 4
4 2
5 5

1
6
12
8
25

8 5
OXXOXXOX
XOXXOXOX
XOOXOOXO
OXOOXOXO
OXXOXXOX
XOXXOXOX
XOOXOOXO
OXOOXOXO
6
7 2
8 1
4 5
8 8
3 4
1 7

5
3
9
14
5
3

提示

$N$、$M$、$X_i$、$Y_i$ 和 $Q$ 为整数。 $1 \le N \le 2000$ $1 \le M \le 2 \times N$ $S_i$ 由 $O$ 和 $X$ 组成。 $1 \le Q \le 2 \times 10^5$ $1 \le X_i,Y_i \le N$只有格子 $(1,1)$ 包含一枚棋子，它覆盖了下列 # 个格子：

标签: AtCoder|abc260G

来源

AtCoder|abc260G