题目描述

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(1 \le G \le 10^5)$ 个私人花园里放牧！约翰利用他的专业法医知识，已经能够确定每个花园被放牧的确切时间。他还确定有一头牛负责了每一次放牧事件。

作为对这些犯罪行为的回应，约翰的 $N(1 \le N \le 10^5)$ 头奶牛都提供了一个证明牛在特定时间处于特定位置的不在场证明。帮助约翰测试每个不在场证明是否证明了牛的清白。

如果一头牛不可能在所有放牧地点和她的不在场证明之间旅行，那么她就可以被确定为清白。牛的行进速度为每单位时间 $1$ 个单位距离。

输入格式（输入从终端/标准输入中获取）：

输入的第一行将包含用空格分隔的 $G$ 和 $N$。

接下来的 $G$ 行包含用空格分隔的整数 $x$，$y$ 和 $t\ (-10^9 \le x, y \le 10^9;\ 0 \le t \le 10^9)$，描述放牧的位置和时间。一头牛始终可以在所有放牧地点之间旅行。

接下来的 $N$ 行包含用空格分隔的整数 $x$，$y$ 和 $t\ (-10^9 \le x, y \le 10^9;\ 0 \le t \le 10^9)$，描述每头牛的不在场证明的位置和时间。

输出格式（将输出打印到终端/标准输出）：

输出一个整数：证明了其清白的具有不在场证明的牛的数量。

说明提示：

有两次放牧；第一次在 $(0,0)$ 的时间是 $100$，第二次在 $(50,0)$ 的时间是 $200$。

第一头牛的不在场证明不能证明她的清白。她只有足够的时间到达第一次放牧地点。

第二头牛的不在场证明证明了她的清白。她离任何放牧地点都很远。

不幸的是，对于第三头牛，身处犯罪现场并不能证明清白。

最后，第四头牛是清白的，因为从她的不在场证明到最后的放牧地点是不可能的。

数据范围

• 输入 $2 \sim 4$：$1 ≤ G, N ≤ 10^3$。此外，对于农场和不在场证明，$-10^6 ≤ x,y ≤ 10^6$ 和 $0 ≤ t ≤ 10^6$。

• 输入 $5 \sim 11$：没有额外的约束条件。

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.