Trees#7386
In the capital city of Olympia, a new Olympic park is being planned within a designated territory. This territory is shaped like a convex polygon. The park designer intends to plant trees in several green zones, which are represented as circles on the map. Each green zone is defined by the coordinates of its center and its radius.
The task is to plant trees at points with integer coordinates that lie within the park (including its boundary) and also within at least one green zone (including its boundary). If a point belongs to multiple overlapping green zones, only one tree should be planted there.
Task
Write a program that, given the coordinates of the polygon's vertices defining the park's territory, and the coordinates and radii of the green zones, calculates the number of trees to be planted.
The first line of the input contains an integer (3 \le N \le 10^5) — the number of vertices of the polygon defining the park's territory. The next lines each contain two integers — the x and y coordinates of the vertices, listed in either clockwise or counterclockwise order. The following line contains an integer (1 \le M \le 50\,000) — the number of green zones. The next lines each contain three integers: the x and y coordinates of the center of a green zone, and its radius. All coordinates are integers within the range from -10^9 to 10^9 inclusive. The radii are positive integers, and the total sum of all radii does not exceed 10^5. Note that some green zones may be entirely within others, and some may lie outside the polygon. Different zones may share centers or even coincide.
Output a single integer on one line — the number of trees that will be planted according to the designer's plan.
Beispiel 1
The test set is divided into blocks with the following additional conditions:
1. of the points: N \le 100. Within this set, there are overlapping test groups:
of the points (of the total): the park is a rectangle with sides parallel to the coordinate axes.
of the points (of the total): N \cdot M \cdot R^2 \le 10^7, where is the largest radius.
of the points (of the total): there exists a square with sides of length , parallel to the coordinate axes, within or on whose boundaries the park's territory lies entirely.
2. of the points: no additional constraints are imposed on the input data.