85 lines
1.3 KiB
Markdown
85 lines
1.3 KiB
Markdown
|
# 捞鱼(fish)
|
|||
|
|
|
|||
|
|
## 题目描述
|
|||
|
|
|
|||
|
|
相信大家做过【Fishes】这题之后对捞鱼都很感兴趣，给1个 $n\times m$ 的鱼池，和一个边长 $r$ 的正方形渔网。鱼池里有 $k$ 条鱼，位置给定。
|
|||
|
|
|
|||
|
|
现在尝试在所有合法位置（渔网必须全部在鱼池内部）撒网，请问能捕到 $x$ 条鱼的位置有多少个，请你输出 $x=0,1,...,k$ 时的所有答案。
|
|||
|
|
|
|||
|
|
## 输入格式
|
|||
|
|
|
|||
|
|
第一行输入4个整数 $n,m,r,k$
|
|||
|
|
|
|||
|
|
接下来 $k$ 行，每行2个正整数 $(x,y)$ 代表1条鱼的位置，可能有重复
|
|||
|
|
|
|||
|
|
## 输出格式
|
|||
|
|
|
|||
|
|
输出 $k+1$ 行，分别代表能捕到 $0,1,...,k$ 条鱼的位置有多少个
|
|||
|
|
|
|||
|
|
## 样例 #1
|
|||
|
|
|
|||
|
|
### 样例输入 #1
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
3 3 2 3
|
|||
|
|
2 1
|
|||
|
|
2 2
|
|||
|
|
2 3
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 样例输出 #1
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
0
|
|||
|
|
0
|
|||
|
|
4
|
|||
|
|
0
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 样例 #2
|
|||
|
|
|
|||
|
|
### 样例输入 #2
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
1000000000 1000000000 10 4
|
|||
|
|
1 1
|
|||
|
|
5000 5000
|
|||
|
|
5001 5001
|
|||
|
|
5000 5000
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 样例输出 #2
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
999999981999999961
|
|||
|
|
20
|
|||
|
|
19
|
|||
|
|
81
|
|||
|
|
0
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 样例 #3
|
|||
|
|
|
|||
|
|
### 样例输入 #3
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
见下发样例
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 样例输出 #3
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 提示
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
对于30%的数据，$n,m\le 1000, r\le10, k\le 10^4$
|
|||
|
|
|
|||
|
|
对于另20%的数据，$n,m\le 10^5, r\le10, k\le10$
|
|||
|
|
|
|||
|
|
对于80%的数据，$n,m\le 10^5, r\le10, k\le 10^4$
|
|||
|
|
|
|||
|
|
对于100%的数据，$1\le n,m\le 10^9, 1\le r\le 10, 1\le k\le 10^4$
|