Jellyfish Nightmare

题意翻译

### 题意 Bob 最近长胖了。为了减轻体重， Bob 决定定期在游泳池里游泳。然而，在他第一次去游泳池的前一天，他做了一个奇怪的梦。在这个梦中， Bob 正沿着泳池的一条泳道游泳，但也有一些水母在他周围游泳。值得一提的是，水母一直是 Bob 最深刻的童年恐惧之一。 让我们为 Bob 的梦假设以下物理模型： 1. 游泳池的泳道是平面上直线 $x=0$ 和直线 $x=w$ 之间的区域， Bob 不能游出泳道，但是他可以触碰边界。 2. 水母非常小，但在 Bob 的梦中，它们非常迅速。每只水母都有它的活动区域。这些区域是各种半径的圆，水母坐在它们的中心。两个水母的活动区域可能重叠，一个活动区域甚至可能完全包含在另一个区域内。 3. Bob 具有凸多边形的形状。 4. 不幸的是，Bob 的超重使他非常笨拙，故他在游泳时无法旋转身体。即整个过程多边形可以向任何方向运动，但是**不能旋转**。 5. 每当 Bob 游进水母的活动区域时，它会立即注意到他刺痛他，使他非常痛苦。我们认为只有凸多边形和圆的交为正面积(S>0)时才算进入水母的活动区域。 6. 一旦水母刺伤了 Bob，它就会愉快地游走，不再对 Bob 造成任何威胁。 Bob 想要游到终点且被刺的次数最少，他将从直线 $y=-h$ 出发，在直线 $y=h$ 结束 ,$h=10^{10}$ ### 输入格式 第一行两个整数 $n$ 和 $w$ $(3\le n\le 200,1\le w\le 30000)$，表示多边形的点数和泳道的宽度。 接下来按照逆时针顺序， $n$ 行每行两个整数 $x_i,y_i(0\le x_i\le w,0\le y_i\le 30000)$ ，表示多边形的一个顶点。 然后 $m$ 行，每行三个整数 $x_i,y_i,r_i(0\le x_i \le w,0\le y_i,r_i\le30000)$，表示水母所在的圆心和圆的半径，保证任意两个水母的圆心不同。 ### 输出格式 一个整数，表示 Bob 最少被刺几次。

题目描述

Bob has put on some weight recently. In order to lose weight a bit, Bob has decided to swim regularly in the pool. However, the day before he went to the pool for the first time he had a weird dream. In this dream Bob was swimming along one of the pool's lanes, but also there were some jellyfish swimming around him. It's worth mentioning that jellyfish have always been one of Bob's deepest childhood fears. Let us assume the following physical model for Bob's dream. 1. The pool's lane is an area of the plane between lines $ x=0 $ and $ x=w $ . Bob is not allowed to swim outside of the lane, but he may touch its bounding lines if he wants. 2. The jellyfish are very small, but in Bob's dream they are extremely swift. Each jellyfish has its area of activity around it. Those areas are circles of various radii, with the jellyfish sitting in their centers. The areas of activity of two jellyfish may overlap and one area of activity may even be fully contained within another one. 3. Bob has a shape of a convex polygon. 4. Unfortunately, Bob's excess weight has made him very clumsy, and as a result he can't rotate his body while swimming. So he swims in a parallel translation pattern. However at any given moment of time he can choose any direction of his movement. 5. Whenever Bob swims into a jellyfish's activity area, it will immediately notice him and sting him very painfully. We assume that Bob has swum into the activity area if at some moment of time the intersection of his body with the jellyfish's activity area had a positive area (for example, if they only touch, the jellyfish does not notice Bob). 6. Once a jellyfish stung Bob, it happily swims away and no longer poses any threat to Bob. Bob wants to swim the lane to its end and get stung the least possible number of times. He will start swimming on the line $ y=-h $ , and finish on the line $ y=h $ where $ h = 10^{10} $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ w $ ( $ 3 \le n \le 200, 1 \le w \le 30000 $ ) — the number of vertices in the polygon that constitutes the Bob's shape and the width of the swimming pool lane. Each of the next $ n $ lines contains two integers $ x_i $ and $ y_i $ ( $ 0 \le x_i \le w, 0 \le y_i \le 30000 $ ) — the coordinates of corresponding vertex of the polygon. The vertices in the polygon are given in counterclockwise order. It is guaranteed that the given polygon is strictly convex. The next line contains an only integer $ m $ ( $ 0 \le m \le 200 $ ) — the number of the jellyfish in the pool. Each of the next $ m $ lines contains three integers ( $ x_i $ , $ y_i $ , $ r_i $ ( $ 0 \le x_i \le w, 0 \le y_i \le 30000, 1 \le r_i \le 30000 $ ) — coordinates of the $ i $ -th jellyfish in the pool and the radius of her activity. It is guaranteed, that no two jellyfish are located in the same point.

输出格式

Output a single integer — the least possible number of jellyfish that will sting Bob.

输入输出样例

输入样例 #1

4 4
0 0
2 0
2 2
0 2
3
1 1 1
3 5 1
1 9 1

输出样例 #1

0

输入样例 #2

4 6
0 0
3 0
3 3
0 3
3
1 0 1
4 2 2
3 6 1

输出样例 #2

2

输入样例 #3

4 2
0 0
1 0
1 1
0 1
2
1 1 1
1 3 1

输出样例 #3

2

说明

Visualization of the possible solutions to the first and the second sample test cases are below: