题目描述

Note: The time limit for this problem is 4s, two times the default.

Somebody has been grazing in Farmer John's $G(1 \le G \le 10^5)$ private gardens! Using his expert forensic knowledge, FJ has been able to determine the precise time each garden was grazed. He has also determined that there was a single cow that was responsible for every grazing incident.

In response to these crimes each of FJ's $N(1 \le N \le 10^5)$ cows have provided an alibi that proves the cow was in a specific location at a specific time. Help FJ test whether each of these alibis demonstrates the cow's innocence.

A cow can be determined to be innocent if it is impossible for her to have travelled between all of the grazings and her alibi. Cows travel at a rate of $1$ unit distance per unit time.

输入格式

The first line of input will contain $G$ and $N$ separated by a space.

The next $G$ lines contain the integers $x, y$, and $t (−10^9 \le x,y \le 10^9;0 \le t \le 10^9)$

separated by a space describing the location and time of the grazing. It will always be possible for a single cow to travel between all grazings.

The next $N$ lines contain $x$, $y$, and $t(−10^9 \le x,y \le 10^9;0 \le t \le 10^9)$ separated by a space describing the location and time of each cow's alibi.

输出格式

Output a single integer: the number of cows with alibis that prove their innocence.

题目大意

题意

有 $g$ 处抓握，第 $i$ 处抓握如 $(x_i,y_i,t_i)(-10^9\leq x_i,y_i\leq 10^9,0\leq t_i\leq 10^9)$，表示 $t_i$ 时刻 $(x_i,y_i)$ 有一处抓握，FJ 抓到了 $n$ 头嫌疑奶牛，每头奶牛都提供了如 $(x_j,y_j,t_j)$ 的证词，表示它 $t_j$ 时刻在 $(x_j,y_j)$，一头奶牛一个单位时间可以移动一个单位距离，奶牛可以洗脱自己的清白，当且仅当它没有足够的时间作出所有的抓握，即，只要它没有足够的时间从它提供的证词的时刻到达随便一个抓握处，它就是清白的。

问有多少奶牛是清白的？

输入格式

第一行输入 $g,n$。

接下来 $g$ 行每行三个整数 $x_i,y_i,t_i$ 表示一处抓握。

接下来 $n$ 行每行三个整数 $x_j,y_j,t_j$ 表示一个证词。

输出格式

一行一个整数表示清白的牛的个数。

2 4
0 0 100
50 0 200
0 50 50
1000 1000 0
50 0 200
10 0 170

2

提示

Explanation for Sample 1

There were two grazings; the first at $(0,0)$ at time 100 and the second at $(50,0)$ at time $200$.

The first cow's alibi does not prove her innocence. She has just enough time to arrive at the first grazing.

The second cow's alibi does prove her innocence. She is nowhere near any of the grazings.

Unfortunately for the third cow, being at the scene of the crime does not prove innocence.

Finally, the fourth cow is innocent because it's impossible to make it from her alibi to the final grazing in time.

SCORING

• Inputs $2-4$: $1 \le G,N \le 10^3$. Also, for both the fields and alibis, $−10^6 \le x,y \le 10^6$ and $0 \le t \le 10^6$.
• Inputs $5-11$: No additional constraints.