QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

#5385. 哥布林花园守卫

Statistics

在一场史无前例的事件中,哥布林最近对 Nedewsian 市的 Mlohkcots 发动了入侵。哥布林——那些矮小的绿色生物——最喜欢做的事情就是给平静有序的人类生活增添混乱。它们几乎什么都不怕,但它们为数不多害怕的东西之一就是水。

Felipe Escobar Bravo, cc-by-nc-nd

哥布林入侵现在已经蔓延到了皇家花园,哥布林们正忙着偷水果、骑着割草机兜风,并将树木雕刻成各种猥琐的形状。Lrac Fatsug 国王下令必须立即停止这种胡闹行为!

值得庆幸的是,花园里配备了自动喷水灭火系统。启动喷水器会淋湿范围内的所有哥布林,迫使它们跑回家把自己弄干。

作为皇家花园卫队的一员,你被要求计算在喷水器开启后,还有多少哥布林会留在皇家花园里,以便皇家园丁们规划下一步行动。

输入格式

输入的第一行包含一个整数 $1 \le g \le 100\,000$,表示皇家花园中哥布林的数量。

接下来 $g$ 行,每行包含两个整数 $0 \le x_i \le 10\,000$ 和 $0 \le y_i \le 10\,000$,表示每个哥布林的位置。花园是平坦的方形,所有距离单位均为米。由于量子干扰,多个哥布林可以占据花园中完全相同的位置。

接下来的一行包含一个整数 $1 \le m \le 20\,000$,表示花园中喷水器的数量。

最后 $m$ 行,每行包含两个整数 $0 \le x_i \le 10\,000$ 和 $0 \le y_i \le 10\,000$,以及一个整数半径 $1 \le r \le 100$,表示该喷水器覆盖的区域。这意味着任何距离点 $(x_i, y_i)$ 不超过 $r$ 的哥布林都会被该喷水器淋湿。

同一个位置可能会有多个喷水器。

输出格式

输出喷水器开启后留在花园里的哥布林数量。

样例

输入格式 1

5
0 0
100 0
0 100
100 100
50 50
1
0 0 50

输出格式 1

4

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.