当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6089:Rikka with Terrorist

题目描述
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

In an ancient country, there are $n \times m$ cities. The coordinate of the $(x-1)m+y$th city is $(x,y)(1 \leq x \leq n,1 \leq y \leq m)$. There are $q$ tourists. Initially, the $i$th tourist is at city $(x_i,y_i)$ and all of them want to go out and play in other cities.

Unfortunately, $K$ of the $n \times m$ cities has been controlled by terrorists, so these $K$ cities became unsafe. For safety, the tourist whose initial coordinate is $(x1,y1)$ can go to the city $(x2,y2)$ if and only if all of the city $(x,y)(\min(x1,x2) \leq x \leq \max(x1,x2),\min(y1,y2) \leq y \leq \max(y1,y2))$ is safe.

Now, for each tourist, Yuta wants to know the number of cities he can reach safely (including the initial city he stayed).

It is too difficult for Rikka. Can you help her?

In the sample, the third tourist can reach $(1,4),(2,4),(3,4),(4,4),(1,3),(2,3),(2,2),(2,1)$.
输入解释
The first line contains a number $t(1 \leq t \leq 100)$, the number of the testcases. There are at least $98$ testcases with $n,m,K,q \leq 10^3$.

For each testcase, the first line contains four numbers $n,m,K,q(1 \leq n,m,K,q \leq 10^5)$.

Then $K$ lines follow, each line contains two numbers $(a_i,b_i)(1 \leq a_i \leq n,1 \leq b_i \leq m)$ -- the coordinate of an unsafe city. It is guaranteed that the coordinates are different from each other.

Then $q$ lines follow, each line contains two numbers $(x_i,y_i)(1 \leq x_i \leq n,1 \leq y_i \leq m)$ -- the initial city of each tourist. It is guaranteed that initially each tourist stays at a safe city.
输出解释
For each tourist, print a single line with a single number -- the answer.
输入样例
1
4 5 4 4
1 2
2 5
3 3
4 5
1 5
2 1
2 4
4 1
输出样例
3
9
8
9
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6089

最后修改于 2020-10-25T23:28:17+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
12000/6000MS(Java/Others) 65536/65536K(Java/Others)