Minimum Sprinklers to Water Garden Beds

You are given a list of garden beds and a set of available sprinklers. Each garden bed is represented by a polygon with its vertices provided on a single line. Each sprinkler is defined by its center coordinates and a radius.

A sprinkler can water a garden bed if and only if every vertex of the garden bed lies inside or on the boundary of the circle defined by the sprinkler. That is, for every vertex \((x, y)\) of the polygon and a sprinkler with center \((x_s, y_s)\) and radius \(r\), the condition \[ (x - x_s)^2 + (y - y_s)^2 \le r^2 \] must hold.

Your task is to determine the minimum number of sprinklers needed such that every garden bed is watered by at least one sprinkler. A sprinkler may water multiple garden beds. If it is impossible to water all garden beds with the given sprinklers, output -1. In the special case when there are no garden beds, output 0.

Note: The input is read from the standard input and the output is written to the standard output.

inputFormat

The input format is as follows:

1. The first line contains an integer \(N\) representing the number of garden beds.
2. The next \(N\) lines each describe a garden bed. Each line starts with an integer \(k\) indicating the number of vertices, followed by \(2\cdot k\) space-separated integers representing the coordinates of the vertices in order.
3. The next line contains an integer \(M\) representing the number of sprinklers available.
4. The following \(M\) lines each contain three space-separated integers: \(x\), \(y\), and \(r\), where \((x, y)\) is the center of the sprinkler and \(r\) is its radius.

All input is provided via standard input.

outputFormat

Output a single integer which is the minimum number of sprinklers needed to water all garden beds if possible, or -1 if it is impossible. The output should be printed to standard output.

2
4 1 1 1 3 3 3 3 1
3 4 4 5 4 4 5
3
2 2 2
4 4 2
4 4 4

2