Jellyfish Nightmare
Contest: Mail.Ru Cup 2018 Round 2
Difficulty rating: 3500

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}$$$.

Input format:
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 format:
Output a single integer — the least possible number of jellyfish that will sting Bob.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
4 4
0 0
2 0
2 2
0 2
3
1 1 1
3 5 1
1 9 1

Example output:
0

Example input:
4 6
0 0
3 0
3 3
0 3
3
1 0 1
4 2 2
3 6 1

Example output:
2

Editorial:
First of all, we will solve a simpler problem: you need to check if it is possible for Bob to swim along the whole lane without any jellyfish stinging him. The position of Bob is identified by the location of his first vertex. Let's find out what are the prohibited areas for it. If a jellyfish had no activity zone and would only sting Bob only if he was swimming over it, the prohibited areas would look like polygons around every jellyfish. If we add the activity zone of radius $$$r$$$, prohibited areas will become "inflated" polygons. To be more precise, if the shape of Bob is a polygon $$$P$$$ they would have a shape of Minkowski sum of a polygon $$$-P$$$ with a circle of radius $$$r$$$. $$$-P$$$ here stands for the polygon inverted relative to the origin.
Now, some of the areas will overlap and prohibit passing between two jellyfishes. If those two jellyfishes have activity areas of radii $$$r_1$$$ and $$$r_2$$$, centered at $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ respectively, Bob may not swim between them if the vector $$$(x_1 - x_2, y_1 - y_2)$$$ belongs to the Minkowski sum of $$$P$$$, $$$-P$$$ and a circle of radius $$$r_1 + r_2$$$. This may be checked by finding the distance from that vector to the polygon $$$P \oplus -P$$$ (here $$$\oplus$$$ stands for Minkowski sum) and comparing it with $$$r_1 + r_2$$$. One thing you need to note here is that at given constraints you can't do those computations in floating point numbers, because the relative difference between $$$r_1 + r_2$$$ and the distance from a vector to a polygon may be as low as $$$10^{-17}$$$. Therefore, you need to do all calculations in integers.
Once you know pair of jellyfishes between which you cannot pass, you also need to find out if you are able to pass between the boundaries of the lane ($$$x=0$$$ and $$$x=w$$$) and the jellyfish. This allows you to construct a graph where every jellyfish and both boundaries are vertices, and the is an edge between two vertices if you cannot pass between them. One may notice that if the left boundary and right boundary are in the same connected component, then it's not possible for Bob to swim without being stung by any jellyfish. It's also possible to prove is that if they are not in the same component, then there is a safe path for Bob.
Returning to the original problem, we may rephrase it like this: remove the least possible number of jellyfishes so that Bob can swim without being stung. This can be solved using min-cut by a standard trick of splitting every vertex corresponding to the jellyfish into two and adding an edge of capacity $$$1$$$ between them. The rest of the edges will have capacity $$$+\infty$$$, left boundary will be the source, and the right boundary will be the target.