← 返回题目列表

Codeforces · 1055/G

G. 水母噩梦

中文机器翻译题面 查看原题

鲍勃最近体重增加了一些。为了减轻一点体重,鲍勃决定定期去游泳池游泳。然而,在他第一次去游泳池的前一天,他做了一个奇怪的梦。在这个梦中,鲍勃沿着泳池的一条泳道游泳,但也有一些水母在他周围游动。值得一提的是,水母一直是鲍勃童年最恐惧的事情之一。

让我们为鲍勃的梦假设以下物理模型。

1. 泳池泳道是 $$$x=0$$$ 线和 $$$x=w$$$ 线之间的平面区域。鲍勃不允许游出泳道,但如果他愿意,他可以触摸泳道的边界线。
2. 水母很小,但在鲍勃的梦中它们速度极快。每只水母的周围都有其活动区域。这些区域是不同半径的圆圈,水母坐在它们的中心。两只水母的活动区域可能重叠,一个活动区域甚至可能完全包含在另一区域内。
3. Bob 的形状是凸多边形。
4. 不幸的是,鲍勃超重的体重使他变得非常笨拙,导致他在游泳时无法旋转身体。所以他以平行翻译模式游泳。然而,在任何特定时刻,他都可以选择移动的任何方向。
5. 每当鲍勃游进水母的活动区域时,水母就会立即注意到他并把他蜇得非常痛苦。如果在某个时刻鲍勃的身体与水母活动区域的交点有一个正面积(例如,如果它们只接触,水母不会注意到鲍勃),我们就假设鲍勃已经游进了活动区域。
6. 一旦水母蜇了鲍勃,它就会高兴地游走,不再对鲍勃构成任何威胁。

鲍勃想游到泳道尽头并尽可能少地被蜇伤。他将从 $$$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$$$ ($$$0 \le m \le 200$$$) — 池中水母的数量。

接下来的 $$$m$$$ 行包含三个整数 ($$$x_i$$$, $$$y_i$$$, $$$r_i$$$ ($$$0 \le x_i \le w, 0 \le y_i \le 30000, 1 \le r_i \le 30000$$$) — 坐标池中的 $$$i$$$ 个水母及其活动半径 保证没有两只水母位于同一点。

输出

输出一个整数——能够蜇鲍勃的水母的最少数量。

示例

输入 #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

注意

第一个和第二个示例测试用例的可能解决方案的可视化如下: