#P16200. [Ncpc2015]Goblin Garden Guards哥布林花园卫士

[Ncpc2015]Goblin Garden Guards哥布林花园卫士

题目描述

哥布林入侵了 Nedewsian 城的皇家花园。哥布林喜欢破坏秩序,但它们害怕水。

幸运的是,花园里安装了自动喷水系统。打开某个喷头后,所有距离该喷头不超过其半径的哥布林都会被淋湿,并立刻跑回家。

你是皇家花园卫队的一员。给定所有哥布林的位置,以及所有喷头的位置和覆盖半径,请计算打开所有喷头后,还有多少只哥布林留在花园里。

输入格式

第一行包含一个整数 gg,表示哥布林数量,满足:

1g100000.1 \le g \le 100000.

接下来 gg 行,每行包含两个整数 xi,yix_i,y_i,表示一只哥布林的位置,满足:

0xi,yi10000.0 \le x_i,y_i \le 10000.

多个哥布林可以位于完全相同的位置。

接下来一行包含一个整数 mm,表示喷头数量,满足:

1m20000.1 \le m \le 20000.

接下来 mm 行,每行包含三个整数 xi,yi,rx_i,y_i,r,表示一个喷头的位置和覆盖半径。满足:

0xi,yi10000,1r100.0 \le x_i,y_i \le 10000, \qquad 1 \le r \le 100.

若某只哥布林到喷头 (xi,yi)(x_i,y_i) 的距离不超过 rr,则它会被淋湿。多个喷头可以位于相同位置。

输出格式

输出一个整数,表示所有喷头打开后仍留在花园里的哥布林数量。

输入输出样例 #1

输入 #1

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

输出 #1

4