Denis holds a Geometers Anonymous Club meeting in SIS. He has prepared n convex polygons…
- User
Denis holds a Geometers Anonymous Club meeting in SIS. He has prepared n convex polygons numbered from 1 to n for the club. He plans to offer members of the club to calculate Minkowski sums of these polygons. More precisely, he plans to give q tasks, the i-th of them asks to calculate the sum of Minkowski of polygons with indices from l_i to r_i inclusive.
The sum of Minkowski of two sets A and B is the set C = \{a + b : a ∈ A, b ∈ B}. It can be proven that if A and B are convex polygons then C will also be a convex polygon.
Sum of two convex polygons
To calculate the sum of Minkowski of p polygons (p > 2), you need to calculate the sum of Minkowski of the first p - 1 polygons, and then calculate the sum of Minkowski of the resulting polygon and the p-th polygon.
For the convenience of checking answers, Denis has decided to prepare and calculate the number of vertices in the sum of Minkowski for each task he prepared. Help him to do it. Input
The first line of the input contains one integer n — the number of convex polygons Denis prepared (1 ≤ n ≤ 100 000).
Then n convex polygons follow. The description of the i-th polygon starts with one integer k_i — the number of vertices in the i-th polygon (3 ≤ k_i). The next k_i lines contain two integers x_{ij}, y_{ij} each — coordinates of vertices of the i-th polygon in counterclockwise order (|x_{ij}|, |y_{ij}| ≤ 10 ^ 9).
It is guaranteed, that there are no three consecutive vertices lying on the same line. The total number of vertices over all polygons does not exceed 300 000.
The following line contains one integer q — the number of tasks (1 ≤ q ≤ 100 000). The next q lines contain descriptions of tasks. Description of the i-th task contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n).
Output
For each task print a single integer — the number of vertices in the sum of Minkowski of polygons with indices from l_i to r_i.
Example
Input
3 3 0 0 1 0 0 1 4 1 1 1 2 0 2 0 1 3 2 2 1 2 2 1 3 1 2 2 3 1 3
Output
5 5 6
Note
Description of the example:
First, second and third polygons from the example Minkowski sums of the first and second, the second and third and all polygons correspondingly
Assistant
We need to compute number of vertices in Minkowski sum of convex polygons over a range [l, r]. Since Minkowski sum is associative and commutative, the order does not matter: the sum of polygons A and B yields a convex polygon whose edges come from the edges of A and B, sorted by angle. Actually, for convex polygons, the Minkowski sum C = A + B has the property that the set of edge directions (or equivalently the outward normals) is the union (with multiplicities) of the edge directions of A and B. More precisely, if you represent a convex polygon by its support function, the sum's support function is the sum. In terms of edges, if A and B are convex with edge vectors (in order), then the edges of C are the sorted list of edge vectors from A and B concatenated. But careful: When adding polygons, the number of vertices of the sum can be less than the sum of vertices of A and B if some consecutive edges are collinear (i.e., same direction). Since input guarantees no three consecutive vertices are collinear within each polygon, each polygon's edge directions are all distinct (actually in a convex polygon, edge directions are in increasing polar angle order, and consecutive edges have distinct directions). However, when summing two polygons, edges from A and B may have the same direction. In the Minkowski sum, such edges will appear combined: you take all edge vectors sorted by angle, and if two edges are collinear (same direction), they merge into a single edge whose length is the sum of lengths. But also if there are multiple edges with same direction from the same polygon? Not possible because each polygon has distinct edge directions (since convex and no three collinear vertices ensures that edges have distinct directions? Actually consider a rectangle: edges are orthogonal, all distinct. For any convex polygon with vertices in CCW order, edge directions are monotonic increasing angle from 0 to 2π, and because no three consecutive collinear, edges cannot have zero length and consecutive edges cannot be collinear. But could non-consecutive edges be collinear? Possibly, if the polygon has parallel edges? In a convex polygon, it's possible to have parallel edges (e.g., a parallelogram has two pairs of parallel edges). Those edges have the same direction but opposite orientation? Wait direction is the direction of the edge vector (from one vertex to the next). In a convex polygon traversed CCW, each edge vector has a direction angle between 0 and 2π (excluding 2π because closed). If polygon has parallel sides, e.g., a parallelogram, two edges are parallel but opposite direction? Actually consider a parallelogram with vertices (0,0), (2,0), (3,1), (1,1). The edge vectors: (2,0) direction 0°, (1,1) direction 45°, (-2,0) direction 180°, (-1,-1) direction 225°. So parallel edges are opposite, not same. In convex polygon, edges all point around; the set of edge directions covers a full rotation; if there is a pair of parallel edges, they would be opposite directions (difference of 180°). So same direction cannot occur within a single polygon because direction increases from 0 to 2π, and after 180°, direction continues increasing; a direction that repeats exactly would mean polygon is not strictly convex? Actually if polygon has two edges with exactly same direction, that would imply two edges are parallel and pointing same direction, which would cause a "flat" region? But that would mean some interior angle is 180°, violating convex? Strict convexity requires interior angles < 180°, but input doesn't guarantee strict convex, only that no three consecutive vertices are collinear. That ensures each interior angle != 180°, but could still have some edges that are parallel but not collinear? Wait if two edges have same direction but are not consecutive, that would mean the polygon has a "zigzag"? But in a convex polygon, the edge directions are strictly increasing as we go around (monotonic from some start to start+2π). Because the polygon is convex, the outward normal rotates monotonically, and the direction of edges (tangent vectors) also rotates monotonically. If two edges have exactly the same direction, then between them the polygon would have to have a change in direction that returns to the same direction, which would break monotonicity. So in a convex polygon, edge directions are all distinct. So each polygon contributes a set of edge directions (angles) that are all distinct.
Thus when summing multiple convex polygons, the edge set of the sum is the multiset union of edges from each polygon, sorted by angle. If two edges from different polygons have exactly the same direction, they combine into one edge whose length is the sum of lengths. So the number of vertices of the sum equals the number of distinct edge directions among all polygons in the sum, but careful: Actually, the Minkowski sum polygon will have one edge for each distinct direction present in the union of edges. Because edges are sorted and if two edges share same angle, they merge. So the number of edges (and vertices) of the sum is the number of distinct edge directions in the combined set.
But is that always? Consider if some polygon has an edge of length zero? No, edges have positive length because vertices distinct and no three consecutive collinear ensures each edge is non-zero. So yes.
Thus problem reduces to: For each query [l, r], we need to count the number of distinct edge directions among all edges of polygons in that range.
But edges are defined by their direction angle (from 0 to 2π). However, angles are real numbers. Since vertices are integer coordinates, edges are vectors (dx, dy) with integer components. The direction can be represented by a reduced direction vector (dx, dy) normalized by gcd: essentially the slope as a rational pair (dx, dy) after reduction and sign? But direction includes orientation; opposite directions are different (since edges are oriented CCW). In convex polygon, edges are oriented in CCW order, so each edge vector points along the boundary direction. When we sum polygons, the Minkowski sum edges are also oriented CCW. The edge vectors from each polygon are taken as is. Two edges from different polygons will merge only if they have exactly the same direction vector (dx, dy) i.e., same orientation and same slope, not just parallel but same direction (since edges are oriented). If they are parallel but opposite direction (dx, dy) vs (-dx,-dy), they are different directions. So we need to consider oriented edge vectors.
Thus each polygon i provides a set of vectors (dx_j, dy_j) for its edges, each integer (since vertices integer). The number of vertices of the Minkowski sum of a set of polygons is the number of distinct vectors (after normalizing to a canonical form) that appear in the union of these edge sets. However, careful: When we sum more than two polygons, does the order of merging affect merging of edges? No, because the Minkowski sum's edge set is exactly the multiset sum of edge vectors, and then merging consecutive collinear vectors (with same direction) yields the final set. Since each polygon individually has no collinear consecutive edges, the final sum's edges are obtained by taking all edge vectors from all polygons, sorting them by angle, and merging collinear ones. So the number of edges in the final polygon = number of distinct directions among the union of all edge vectors.
Thus answer for query = count of distinct direction vectors from all edges of polygons in [l, r].
Now constraints: n up to 100k, total edges up to 300k, q up to 100k. So we need to answer many range distinct count queries offline. Classic problem: count number of distinct elements in subarray (range). We can use Mo's algorithm or offline BIT/segment tree with last occurrence. Since n is up to 100k, edges total 300k, but each polygon contributes many edges; the array we need to query is over polygons, but each polygon yields a multiset of edges (multiple edges). We need to count distinct direction vectors across all edges of polygons in range. This is like: We have a list of items (edges) each belonging to a polygon index. For a range of polygon indices, we need to count how many distinct direction vectors appear among all edges whose polygon index is in [l, r].
We can treat each direction vector as a "color", and each edge as an occurrence of that color. For each query [l, r], we need the number of colors that have at least one occurrence within polygons in that range.
This is essentially distinct count over a collection of intervals (each polygon is a set of edges). The total number of edges is up to 300k, which is moderate.
We can answer using offline queries with BIT: Sort queries by r (right endpoint) and maintain last occurrence of each color (direction vector) in terms of the latest polygon index that contributed that color. But note: A polygon may contain multiple edges with same direction? Within a single polygon, edge directions are distinct, so at most one edge per direction per polygon. However it's possible that a polygon could have the same direction as another polygon? Yes, that's what we count distinct across range.
Thus each direction appears at most once per polygon (actually zero or one times). But each polygon can have at most its number of edges distinct directions, but they are all different within the polygon.
We can think of each polygon i as a set of direction vectors D_i. For a query [l, r], we need |∪_{i=l}^r D_i|.
This is a classic problem of counting distinct elements over sets in ranges, where each set has multiple elements, and total size of sets is sum |D_i| ≤ 300k.
We can process queries offline by scanning r from 1 to n, and maintaining a BIT over indices (polygon indices) that allows us to query how many distinct elements have their last occurrence in [l, r]? Standard approach: For each color c, keep last index where it appeared. When we process polygon i, for each direction d in D_i, we update: if d had a previous last occurrence at prev, we subtract 1 at prev (i.e., BIT add -1 at prev), then add +1 at i, and set last[d]=i. After processing all edges of polygon i, we answer all queries with r = i: answer = queryBIT(l, r) = sum over indices from l to i of BIT, which counts the number of distinct colors whose last occurrence is in that range, which equals number of distinct colors appearing in [l, i] because each color is counted exactly at its latest occurrence within [l, i]. Indeed, standard distinct count query on array can be adapted for "sets per index". As long as we treat each occurrence per index as possibly multiple colors, but we update per color.
Complexity: For each polygon i, we iterate over its edges (directions). For each direction d, we do at most two BIT updates (if last[d] exists, subtract; then add at i). BIT point updates and prefix sum queries O(log n). Total updates = O(total edges) * 2 = 600k, acceptable. Queries q = 100k, each O(log n). So overall O((total edges + q) log n) which is fine.
We need to map direction vectors to IDs (integers) for quick last occurrence tracking. Since total edges ≤ 300k, number of distinct direction vectors across all polygons is at most 300k (maybe less). We can compute a canonical representation for each edge vector: (dx, dy). However, need to ensure that opposite vectors are considered different? Yes, because direction matters. So we can just store (dx, dy) as is without normalization? But note: Two edges that are the same oriented vector (dx,dy) must be considered same direction. However, there is a nuance: For Minkowski sum, edges with same direction but possibly different lengths will merge. So we only care about direction, not length. So we should normalize the vector to a canonical direction representation that ignores length. So we can reduce (dx, dy) by dividing by gcd(|dx|,|dy|) and ensuring a consistent sign? Actually direction is defined by the vector; for merging, if two edges are parallel and same orientation, they merge. So we need to consider the unit direction. So we can compute the reduced direction as (dx/g, dy/g) where g = gcd(dx,dy) (always positive gcd). But we also need to consider sign: For example, vector (-2,0) reduced to (-1,0) is different from (2,0) reduced to (1,0). That's fine.
Potential issue: For vectors (dx, dy) with dx=0, dy positive vs negative, gcd works: (0, dy) reduce to (0, sign) dividing by |dy| yields (0,1) or (0,-1). So that distinguishes orientation.
Thus we can map each edge to a pair (rx, ry) where (dx,dy) reduced to primitive integer vector.
But careful: Since vertices are given in CCW order, edge vectors are oriented accordingly. This is consistent.
Now, is there any case where edges with same direction but opposite orientation could appear from different polygons? Yes. They are distinct directions.
Thus algorithm:
- Read n.
- For each polygon i from 1..n:
- Read k_i.
- Read k_i points (x_j, y_j).
- Compute edge vectors: for j from 0 to k_i-1, vector from point j to point j+1 (mod k). But since order is CCW, edges are taken in that order.
- For each edge, compute dx = x_{j+1} - x_j, dy = y_{j+1} - y_j.
- Reduce to primitive: g = gcd(|dx|, |dy|); if g==0? can't happen because edges non-zero. dx' = dx/g, dy' = dy/g.
- Store this reduced vector as a key for the polygon's edge directions set. Since polygon has no duplicate directions within itself, we could store them as list; but need to ensure we don't duplicate if polygon somehow had same direction twice? Not possible, but we can still handle duplicates by deduplication per polygon? Actually if there were duplicates within a polygon, they would merge within the polygon? But input guarantees no three consecutive collinear, but could two non-consecutive edges be parallel same direction? As argued, not possible. So we can assume per polygon edges distinct directions. But we can still store as set per polygon to be safe, but total edges is 300k, it's okay to just store all edges and later when processing polygon i, we will update for each edge direction; however, if a polygon contains the same direction twice (shouldn't happen), we would update twice for same color, causing double subtraction/addition? That could mess up the distinct count because we treat each occurrence as a separate color occurrence, but color appears twice in same polygon. In the distinct counting approach, we want to consider that the polygon contributes that direction, regardless of multiplicity. But if we process each edge separately, we would first process first occurrence: last[d]=some previous index, we subtract at prev, add at i, set last[d]=i. Then process second occurrence: last[d] is now i (since we just updated), so we would subtract at i (remove the +1 we just added) and then add at i again (so net 0? Actually we would do: if last[d] exists, BIT.add(last[d], -1). That would subtract the +1 we just added at i. Then BIT.add(i, +1). So net effect is BIT.add(i,0) effectively, but we also set last[d]=i again. This would result in the color still counted once. However, careful: If there are multiple edges with same direction in the same polygon, the polygon still contributes that direction only once to the union. Our processing with duplicate edges would result in the same final state as if only one edge: after processing all duplicates, last[d]=i, and BIT has +1 at i (since the last add sets +1). But the intermediate subtract might cancel earlier adds. Let's simulate: Suppose last[d]=prev. Process first edge: BIT.add(prev, -1), BIT.add(i, +1), last=d i. Process second edge: BIT.add(i, -1) (since last is i), BIT.add(i, +1), last stays i. So net effect: BIT.add(prev, -1) from first; BIT.add(i, +1) from first; BIT.add(i, -1) from second; BIT.add(i, +1) from second = BIT.add(prev, -1) and BIT.add(i, +1). So still only one +1 at i. So it's fine: duplicates within same polygon don't change final state (they result in the same as one occurrence). However, there might be an issue if the polygon has the same direction multiple times and we do updates sequentially: we end up subtracting at i and re-adding, causing unnecessary operations but correct final. So we can just store all edges as they come, without dedup per polygon. That's simpler.
Thus store for each polygon i a list of reduced vectors (keys). We'll process sequentially.
Now we need to map each reduced vector to an ID (int) for array last[] size up to distinct count ≤ 300k. Use dictionary (hash map) from tuple (dx', dy') to integer id.
Edge cases: The polygon might be given with points in CCW order. The edge vectors are computed correctly. The sum polygon's number of vertices is exactly the number of distinct direction vectors. However, is there any nuance about collinearity after merging? The Minkowski sum of convex polygons yields a convex polygon. The number of vertices equals number of edges, which equals number of distinct edge directions as argued. But is it always true that the number of vertices equals number of distinct edge vectors? Let's double-check with examples.
Consider two convex polygons: a triangle and a rectangle. Triangle edges: vectors (1,0), ( -1,1 ), (0, -1) (example). Rectangle: (0,1), ( -1,0 ), (0,-1), (1,0). Distinct directions: (1,0), (-1,1), (0,-1), (0,1), (-1,0). That's 5, output 5? Possibly.
But there is a nuance: When summing, the order of edges sorted by angle yields a closed polygon. If we just take distinct directions, does it guarantee that the polygon will have exactly one edge per direction? Consider that the sum of edge lengths in each direction equals total length of that direction's contributions. But what about directions that are exactly opposite? They are separate edges because they point in different directions. For a convex polygon, the edge direction angles increase strictly from 0 to 2π. So if we have a set of direction vectors (distinct angles) that cover the full 2π? Actually, the sum polygon must be closed: the sum of all edge vectors must be zero. If we take all polygons' edges merged, the multiset of edge vectors already sums to zero because each polygon's edges sum to zero individually, so the combined multiset also sums to zero. After merging collinear edges, the resulting set of vectors (with summed lengths) will also sum to zero. But will the sorted angles necessarily cover a full 2π? Yes, because the union of directions from all polygons may not cover all angles; but the resulting polygon may have edges only in some angular sectors? However, a convex polygon must be closed and its edges' direction angles must span a full 360 degrees (i.e., sum of rotations around). Actually, for any convex polygon, the sequence of outward normals (or edge directions) must cover a full circle: as you traverse the polygon, you turn left continuously, totaling 360 degrees. The edge directions (as vectors) are the tangents; their directions must also cover a full 360 degrees, but not necessarily uniformly. More precisely, the turning angle from one edge to the next is positive (interior angle < 180°, so external turning is positive). The sum of turning angles is 2π. So the edges' direction angles are strictly increasing modulo 2π, covering a full cycle. Thus the set of edge directions must be such that when sorted, the angular differences sum to 2π. However, if we simply take a set of direction vectors, is it guaranteed that after merging collinear ones, the remaining directions can be ordered such that the polygon closes? Actually, the Minkowski sum polygon's edge set is exactly the set of distinct directions present in the union, with lengths being the sum of lengths of all edges in that direction from all summands. Since each individual polygon is closed, the total sum of vectors in each direction across all polygons is zero when summing over all directions with appropriate lengths. After merging, we have a list of distinct directions with lengths L_d > 0 (since each direction appears at least once). The sum over all d of L_d * unit_vector(d) = 0. For the polygon to be valid (closed), this condition must hold. It does hold because it's derived from the sum of closed polygons. Also, the directions must be such that when sorted by angle, they traverse a full 360 degrees. Could it be that the set of directions does not cover a full circle? Suppose all polygons are symmetric such that after summing, some directions may cancel? But lengths are positive, so each direction contributes a positive length. The only way the sum of vectors can be zero is if the vectors are not all in a half-plane; they must be balanced. Indeed, for a set of vectors with positive lengths, if their directions all lie within a half-plane, the sum cannot be zero (it would have a component). Therefore, the directions must span more than 180 degrees, but do they necessarily cover exactly 360? Could there be gaps (angles with no edge) and still the polygon closes? Yes, in a convex polygon, you can have edges with certain directions and then you turn from one direction to another with a positive turning angle; that turning angle corresponds to a corner. If there is a gap of angle θ between two consecutive edges in sorted order, that means the polygon has a vertex where the direction changes by θ, which is fine; it's just a corner with interior angle π - θ? Wait careful: The polygon's vertices correspond to changes in direction. The edges are straight segments. If we have edges with directions d1, d2, ..., dk in CCW order (angles increasing), the polygon will have a vertex between edge i and i+1 where the direction changes by Δθ_i = angle(d_{i+1}) - angle(d_i) (mod 2π). This Δθ_i is the external turning angle. It must be >0 because convex. The sum of all Δθ_i = 2π. So it's possible that there are large gaps between directions, but that's fine; they just correspond to vertices with larger turning angles. So the number of edges equals the number of distinct directions, as each direction contributes exactly one edge. So our approach stands.
Thus answer = number of distinct reduced direction vectors among polygons in range.
Now implement:
- Parse input.
- For each polygon i:
- Read k and points.
- Compute edge vectors.
- For each, reduce to primitive.
- Append to list edges_by_poly[i] (maybe store as list of IDs).
- Use dict to assign ID.
But careful: total edges 300k, storing all edges_by_poly as list of lists is okay.
-
Then we have q queries: (l, r). We'll store for each r, list of queries (l, index).
-
We need BIT of size n (1-indexed). BIT supports point add and prefix sum.
-
Initialize last array of size distinct_count+1 (or map from color id to last polygon index, default 0).
-
Process i from 1 to n:
- For each direction id in edges_of_poly[i]:
- prev = last[id]
- if prev != 0: BIT.add(prev, -1)
- BIT.add(i, +1)
- last[id] = i
- After processing polygon i, for each query with r == i:
- ans[idx] = BIT.sum(i) - BIT.sum(l-1) (range sum l..i) Actually, BIT stores point contributions at indices representing last occurrence of each color. The prefix sum up to i gives total distinct colors with last occurrence ≤ i, which is exactly total distinct colors in [1,i]. For query [l,i], we need colors whose last occurrence is in [l,i], which is prefix(i) - prefix(l-1). So correct.
- For each direction id in edges_of_poly[i]:
Edge Cases: Polygon i might have no edges? But k_i >= 3, so at least 3 edges.
Complexities: O((total edges + q) log n) ~ 400k * log(100k) ~ few million, fine.
Now we must ensure correctness of direction reduction: For edge vector (dx, dy), we compute g = gcd(|dx|, |dy|). Since dx,dy can be negative, we reduce by g, keeping signs. But we need a canonical representation for the direction. For example, vector (2,0) reduces to (1,0); (-2,0) to (-1,0). That's fine.
But what about (0, -4) reduce to (0, -1). However, note that in the Minkowski sum, if we have two edges with vectors (0,1) and (0,-1), they are opposite directions and do not merge. So separate.
Thus mapping tuple (dx/g, dy/g) works.
Potential overflow: coordinates up to 1e9, differences up to 2e9, but gcd of numbers up to 2e9 fits in 64-bit. We'll use Python's integers, no problem.
Now need to be careful about the orientation: In convex polygon given CCW, edge vectors are oriented CCW. Is it possible that some polygon might be given in clockwise order? The statement says "in counterclockwise order", so it's CCW.
Thus the edges we compute are correct.
Now verify with example.
Example: Polygon1: triangle (0,0), (1,0), (0,1). Edges: (1,0) -> (1,0) (0,1)-(1,0) = (-1,1) (0,0)-(0,1) = (0,-1) but careful: order: vertices: v0=(0,0), v1=(1,0), v2=(0,1). CCW. Edge0: v1 - v0 = (1,0). Edge1: v2 - v1 = (-1,1). Edge2: v0 - v2 = (0,-1). Reduced: (1,0), (-1,1), (0,-1).
Polygon2: 4 vertices: (1,1),(1,2),(0,2),(0,1). Edges: (1,2)-(1,1) = (0,1) (0,2)-(1,2) = (-1,0) (0,1)-(0,2) = (0,-1) (1,1)-(0,1) = (1,0) Reduced: (0,1), (-1,0), (0,-1), (1,0). Distinct: (1,0), (-1,1) from first? Actually polygon2 has (0,1),(-1,0),(0,-1),(1,0). So union with polygon1: (1,0), (-1,1), (0,-1), (0,1), (-1,0). That's 5 distinct. Query 1 2 -> answer 5. Matches sample first output 5.
Polygon3: (2,2),(1,2),(2,1). Wait vertices: 2,2; 1,2; 2,1. That's triangle? Edges: (1,2)-(2,2) = (-1,0) (2,1)-(1,2) = (1,-1) (2,2)-(2,1) = (0,1)? Actually careful: vertices in order: given 3 points: (2,2), (1,2), (2,1). Is that CCW? Let's compute: (2,2) -> (1,2) -> (2,1). Compute orientation? Might be CW? But statement says CCW. We'll trust sample. Edges: v1-v0 = (1-2,2-2)=(-1,0) v2-v1 = (2-1,1-2)=(1,-1) v0-v2 = (2-2,2-1)=(0,1) Reduced: (-1,0), (1,-1), (0,1). Note (1,-1) is direction (1,-1). That's distinct. Union of polygons 2 and 3? Query 2 3: polygons 2 and 3. Polygon2 directions: (0,1),(-1,0),(0,-1),(1,0). Polygon3: (-1,0), (1,-1), (0,1). Distinct: (0,1), (-1,0), (0,-1), (1,0), (1,-1). That's 5, output 5. Matches second output 5.
Query 1 3: union all three: add polygon1's (1,0),(-1,1),(0,-1). Already have (0,-1),(1,0). New: (-1,1). Also polygon1 has (0,-1) but already there; (1,0) already. So distinct set = (1,0), (-1,1), (0,-1), (0,1), (-1,0), (1,-1). That's 6 distinct. Output 6. Matches.
So approach works.
Thus solution: Count distinct edge direction vectors over range.
Now we must ensure that no other nuance: Is the number of vertices always equal to number of distinct edge directions? Consider case where after merging edges, there may be a scenario where two consecutive edges after merging are collinear? By definition merging ensures no two consecutive have same direction, so number of edges = number of distinct directions. However, could there be a scenario where a direction appears but its total length becomes zero? No, length positive.
Thus answer is simply count of distinct reduced vectors.
Now implement details:
We'll read input using sys.stdin.buffer.read() for speed, parse integers.
We'll store:
poly_edges = [] (list of list of ints (color IDs)). We'll first assign IDs as we parse polygons, but we need dict mapping from reduced vector tuple to ID. We can assign IDs on the fly. While parsing polygon i, compute each reduced vector, get or assign ID, append to list for polygon i. Then later process.
Alternatively, we can combine processing and scanning: Since we need to process queries offline sorted by r, we can parse all polygons, store edges per polygon as IDs. Then do BIT processing.
Memory: total edges ≤ 300k, storing as list of ints per polygon is okay.
Implementation steps:
- Read n.
- For i in range(1, n+1): read k_i. read k_i points into list of (x,y). compute edges: for j in range(k_i): dx = x[(j+1)%k_i] - x[j] (but careful: we need to store each edge; we can compute on the fly without storing all points by reading sequentially and keeping previous point.) Better: read points sequentially, compute edge from previous to current, but we need first edge from last to first. So we can store points in a list.
Since total points ≤ 300k, storing temporarily per polygon is okay.
Simplify: For each polygon, read all points into list pts. Then for j in range(k): dx = pts[(j+1)%k][0] - pts[j][0] dy = pts[(j+1)%k][1] - pts[j][1] reduce: g = math.gcd(abs(dx), abs(dy)) (math.gcd works for positive ints, pass abs values) if g == 0: impossible. dx //= g; dy //= g key = (dx, dy) if key not in map: assign new id = len(map)+1 (starting 1) poly_edges[i-1].append(id)
But we need poly_edges indexed from 0 or 1; we can use 0-indexed but queries are 1-indexed. We'll process from i=0 to n-1 but convert to 1-indexed in BIT.
Simplify: Keep poly_edges as list of lists, with index i (0-based). In BIT we use 1-indexed indices; when processing polygon i (0-based), we treat its BIT index as i+1.
We'll store queries: for each r (1-indexed) we need list of (l, query_idx). We'll group by r.
Processing:
last = array of size distinct_count+1, initialized to 0. bit = BIT(n) (size n)
for i in range(1, n+1): # 1-indexed polygon index for color_id in poly_edges[i-1]: prev = last[color_id] if prev != 0: bit.add(prev, -1) bit.add(i, 1) last[color_id] = i for (l, idx) in queries_by_r[i]: ans[idx] = bit.sum(i) - bit.sum(l-1)
Finally print each answer in order.
BIT implementation:
class BIT: def init(self, n): self.n = n self.bit = [0]*(n+2) def add(self, idx, delta): while idx <= self.n: self.bit[idx] += delta idx += idx & -idx def sum(self, idx): s=0 while idx>0: s+=self.bit[idx] idx -= idx & -idx return s
Now, we must ensure that the mapping of direction vectors to IDs is consistent across polygons. We'll use a dict: dir_to_id = {}.
Edge Cases:
- Large coordinates, but gcd works.
- Direction vectors may be large, but as reduced they become small (since they are primitive). However, duplicates across polygons with same direction will map to same ID.
Now complexity is fine.
But wait: Is it always true that the number of vertices equals number of distinct edge directions? Let's double-check with more complex cases: Suppose we sum two polygons that have edges with the same direction. After merging, that direction appears once. The number of vertices equals number of edges, which equals number of distinct directions. However, is it possible that after merging, there is a vertex that corresponds to a direction change of zero? No.
But what about the possibility that after summing, some edges may have zero length? No, because each edge direction appears at least once with positive total length (since each polygon contributes positive length edges). So no.
Consider degenerate case where all polygons are such that the sum of lengths in some direction cancels? Cancellation does not happen because lengths are added, not subtracted. So positive.
Thus answer is distinct count.
Now, we should also consider that the Minkowski sum of convex polygons may result in a polygon with fewer edges than the distinct directions if some direction's total length becomes zero? Not possible.
Thus solution is correct.
Now let's think about potential pitfalls: The input guarantee "no three consecutive vertices lying on the same line." This ensures that within each polygon, consecutive edges are not collinear, but it doesn't guarantee that non-consecutive edges cannot be collinear. However, as argued, in a convex polygon, edge directions are strictly increasing in angle, so no two edges have the same direction. So distinct directions per polygon.
Now, confirm that the Minkowski sum of multiple convex polygons indeed has edges that are the union (with multiplicities) of edges from each polygon, sorted by angle, merging collinear ones. That's a known property: The support function of the sum is the sum of support functions. The edges correspond to angles where the support function is not differentiable; the set of such angles is the union of the sets from each summand. So the number of edges is the number of angles in the union, i.e., distinct edge normals. But edge normals are outward normals, not edge directions. However, for a convex polygon given in CCW order, the edge direction vector is rotated 90° from the outward normal? Actually, the outward normal is perpendicular to the edge. But the set of edge directions is in one-to-one correspondence with the set of outward normals (just rotate by 90°). So distinct edge directions equivalent to distinct outward normal directions. So number of edges is number of distinct normals.
Thus all good.
Now we can implement.
But careful: The Minkowski sum is defined for sets, not necessarily polygons with vertices? But we treat them as polygons.
Now test with simple cases:
n=1, single polygon. Then queries always ask that polygon. Answer should be number of vertices of that polygon, because Minkowski sum of just one polygon is itself, and number of vertices equals number of edges which equals number of distinct directions (since no collinear consecutive). So answer = k_i. Our algorithm: For polygon i, we add its edge directions to BIT. When query [i,i], answer = number of distinct directions among its edges = k_i. Works.
Now consider two identical squares. Square A: edges (1,0), (0,1), (-1,0), (0,-1). Square B same. Distinct directions = 4. So answer = 4. Our algorithm: After processing polygon1, BIT at index1 has +1 for each direction? Actually we process each direction: For each color, last becomes 1, BIT[1] gets +1. So after polygon1, BIT sum up to 1 = 4. After polygon2, for each direction, prev = 1, so we subtract at 1, add at 2, last=2. So after polygon2, BIT: index1: 0, index2: 4. So query [1,2] => sum(2)-sum(0)=4 => correct. Query [1,1] => sum(1)-sum(0)=4? Wait after processing polygon2, BIT at index1 is 0, so sum(1) would be 0? But query [1,1] has r=1, but if we answer queries after processing r, for r=1 we already answered before processing polygon2? In offline method, we answer queries with r=i after processing polygon i. So for query [1,1], it would be answered when i=1, giving 4. Good. For query [2,2], answered when i=2, sum(2)-sum(1)=4-0=4. Good.
Now consider two polygons with overlapping directions and some unique. Works.
Thus algorithm is sound.
Now implement in Python. However, constraints up to 100k polygons and 300k edges total; q=100k. Using Python with BIT and loops should be fine, but must be efficient (use fast I/O, avoid heavy overhead per edge). Python's math.gcd is fast enough. We need to parse input quickly: use sys.stdin.buffer.read() and map to ints. Then iterate.
Implementation details:
- Read all ints via data = list(map(int, sys.stdin.buffer.read().split()))
- Use iterator.
We know n first, then for each polygon: read k, then 2*k ints for points.
But careful: The input includes q and queries after polygons.
We'll parse like:
it = iter(data) n = next(it) poly_edges = [] # list of list of color ids dir_to_id = {} for i in range(n): k = next(it) points = [] for j in range(k): x = next(it); y = next(it) points.append((x,y)) # compute edges for this polygon edge_ids = [] for j in range(k): x1, y1 = points[j] x2, y2 = points[(j+1)%k] dx = x2 - x1 dy = y2 - y1 g = math.gcd(abs(dx), abs(dy)) dx //= g dy //= g key = (dx, dy) if key not in dir_to_id: dir_to_id[key] = len(dir_to_id) + 1 # 1-indexed id edge_ids.append(dir_to_id[key]) poly_edges.append(edge_ids)
After all polygons, read q = next(it). Then for i in range(q): l = next(it); r = next(it); store queries.
We need to store queries grouped by r. Since n up to 100k, we can create a list of lists of (l, idx) of length n+1 (1-indexed). queries_by_r = [[] for _ in range(n+1)].
Then for idx in range(q): l = next(it); r = next(it); queries_by_r[r].append((l, idx))
Initialize ans = [0]*q.
Then process:
distinct_cnt = len(dir_to_id) last = [0]*(distinct_cnt+1) # id starts at 1 bit = BIT(n)
for i in range(1, n+1): for color in poly_edges[i-1]: prev = last[color] if prev != 0: bit.add(prev, -1) bit.add(i, 1) last[color] = i for (l, idx) in queries_by_r[i]: ans[idx] = bit.sum(i) - bit.sum(l-1)
After loop, print each ans on separate line.
Now test with sample.
But need to ensure math.gcd: from math import gcd. In Python 3.5+, math.gcd works with nonnegative numbers, we pass abs.
Now, check for potential pitfalls: The BIT sum(l-1) when l=1 uses sum(0) which is 0. Works.
Edge Cases: Polygon might have large number of vertices (like 300k total) but each polygon small; loop over each polygon's edges is okay.
Now complexity: For each edge, we do dictionary lookup and BIT operations. Should be fine.
But is there any scenario where the number of distinct directions is less than the sum but still not equal to the number of vertices? Let's double-check with a more rigorous reasoning:
Given convex polygons P1,...,Pm, each described by its set of edge vectors E_i (with lengths). The Minkowski sum Q = P1+...+Pm has edge set equal to the set of directions that appear in ∪_i E_i, and for each such direction d, the edge length is sum of lengths of edges in that direction from all polygons. The vertices of Q correspond to the points where the direction changes. The number of edges (and vertices) equals |∪ directions|, provided that the sum of vectors in these directions is zero, which it does. However, there is a subtlety: if the directions do not cover a full 360°? Actually the sorted directions will always cover a full 360°? Not necessarily. But the polygon will still have those edges and the turning angles between them will sum to 360°. For example, if you have just two directions opposite each other, you cannot form a closed polygon because sum of vectors would be along that line unless lengths balance to zero, but they would cancel only if lengths equal; but with both lengths positive, they cannot sum to zero unless you have other components. However, the set of directions from polygons individually might not be such that the total lengths produce a closed polygon? But because each polygon is closed, the total sum of vectors per direction from all polygons is zero. So the total length in each direction is determined. It's possible that the set of directions includes some but the vector sum is zero. For instance, consider two polygons: one is a triangle with edges (1,0), (-1,1), (0,-1). Another is a triangle with edges (-1,0), (1,-1), (0,1). Combined directions: (1,0), (-1,1), (0,-1), (-1,0), (1,-1), (0,1). That's 6 directions. Could there be a scenario where the total length in some direction is zero? That would require sum of lengths from all polygons in that direction to be zero, but each contributes nonnegative length; only possible if no polygon has that direction. So all directions present have positive total length.
Now, can the Minkowski sum polygon have fewer vertices than the number of distinct directions? Suppose we have directions that, when sorted, some consecutive directions have an angular difference of exactly π? That's not a problem; it just gives a straight angle? Actually if the angular difference is exactly π, that would be a 180° turn? In a convex polygon, the external turning angle must be less than π (180°) because interior angle >0 and <π? Actually convex polygon can have interior angle up to (but not including) 180°? Strict convexity would require <180°, but general convex allows 180°? The problem says convex polygons and no three consecutive collinear. That ensures interior angles are not 180°, but could be exactly 180°? No three consecutive collinear means you cannot have an interior angle of 180°, because that would mean three consecutive points are collinear. So interior angles are strictly less than 180°, thus external turning angles are strictly between 0 and π (exclusive). So if two consecutive edge directions differ by exactly π, that would mean the polygon turns by 180°, interior angle 0? Actually external turning of π corresponds to a reversal of direction, which would cause a "spike"? Not convex. So in a convex polygon, the edge directions must be strictly increasing by less than π at each step. The sum of all changes is 2π. So each angular gap between consecutive distinct directions must be less than π? Actually for convex polygon, each exterior angle (turning angle) is positive and less than π, but could be any positive value? Could it be greater than π? Consider a very "sharp" corner: interior angle close to 0, exterior angle close to π. That's possible? In a convex polygon, interior angle <180°, so exterior angle >0° and can be up to 180°? Exterior angle = 180° - interior angle. If interior angle can be arbitrarily close to 0°, exterior angle can be close to 180°. So it could be up to but not including 180° (since interior >0). So angular difference can be arbitrarily close to π, but not equal to π because that would require interior angle 0, which would mean collinear consecutive edges? Actually if interior angle is 0, that would mean the polygon turns back on itself, which would create a degenerate polygon (area zero). So not allowed. So angular differences are in (0, π). So as long as distinct directions are sorted, the differences are positive. So number of vertices equals number of distinct directions. No merging beyond collinear.
Thus our method stands.
Now we must consider the possibility that the Minkowski sum of multiple polygons may have vertices where more than two edges merge? That's essentially the merging of collinear edges; we already accounted.
Now we should also consider if any polygon has a direction that is exactly opposite of another direction from same or other polygons? That's fine; they are distinct.
Thus problem solved.
Now we should check time constraints: total edges 300k, BIT updates per edge: up to 2 updates each O(log n) ~ 17. So ~10 million operations, plus dictionary lookups. Python should handle within 2 seconds? Might be borderline but likely okay with optimized code (use sys.stdin.buffer, avoid function call overhead inside loops?). Possibly fine.
But we can micro-opt: Use local variables for BIT methods, inline? Might not be needed.
We can also compress the mapping of color IDs to integers as we did.
Potential improvement: Since each polygon has distinct directions, we could store them as set to avoid duplicate processing within same polygon. But duplicates not present. However, if a polygon accidentally had duplicate direction due to input error? Not according to problem constraints (no three consecutive collinear, but non-consecutive could be same direction? Could it? As argued, edge directions are strictly increasing angle for convex polygon; if two non-consecutive edges had the same direction, then between them the angle would have to increase then come back to same, which would break monotonicity. So it's impossible. So we can skip dedup.
Now we should test with some random data to ensure.
Now possible corner: When computing gcd of (dx, dy) with negative numbers, we used abs. That yields a primitive vector with sign preserved. Good.
Now another nuance: Are edges defined as vectors from one vertex to the next? That yields directed edges consistent with polygon orientation. However, if the polygon is given in CCW order, the edge vectors are oriented accordingly. But what if the polygon is not strictly convex? The problem states convex polygons. So okay.
Now let's double-check sample again with our algorithm: After processing polygon1, we have directions IDs: (1,0) -> id1, (-1,1)->id2, (0,-1)->id3. last[1]=1,last[2]=1,last[3]=1; BIT[1]=3. Queries with r=1: only query 1 3? Actually sample queries: 1 2, 2 3, 1 3. So r=2,3,3. For r=2: after processing polygon2: directions: (0,1) id4, (-1,0) id5, (0,-1) id3, (1,0) id1. For id4: prev=0 -> add at 2; last=2. id5: prev=0 -> add at 2; last=2. id3: prev=1 -> subtract at 1, add at 2; last=2. id1: prev=1 -> subtract at 1, add at 2; last=2. After processing polygon2, BIT: index1: 3 -2 =1? Actually initially BIT[1]=3 (from polygon1). Then we do updates: for id3: subtract at 1 -> BIT[1] becomes 2; add at 2 -> BIT[2] becomes +1 (initially 0). For id1: subtract at 1 -> BIT[1] becomes 1; add at 2 -> BIT[2] becomes 2. For id4: add at 2 -> BIT[2] becomes 3. For id5: add at 2 -> BIT[2] becomes 4. So BIT[1]=1, BIT[2]=4. So total distinct up to 2 = BIT.prefix(2) = 5. Good. For query [1,2] -> prefix(2)-prefix(0)=5. Actually we compute prefix(2)-prefix(0) if l=1: prefix(2)-prefix(0) =5. Works. For [2,2] would be prefix(2)-prefix(1)=5-1=4? But sample doesn't have.
After polygon3: process directions: (-1,0) id5, (1,-1) id6, (0,1) id4. For id5: prev=2 -> subtract at 2, add at 3; id6: new -> add at 3; id4: prev=2 -> subtract at 2, add at 3. After updates: BIT[2] was 4, after subtract id5: BIT[2]=3, add id5 at 3: BIT[3] increases; subtract id4: BIT[2]=2; add id4 at 3; add id6 at 3. So final BIT: index1=1, index2=2, index3=3? Let's compute: Initially after polygon2: BIT[1]=1, BIT[2]=4. Process:
- id5: subtract at 2: BIT[2]=3; add at 3: BIT[3]=1.
- id6: add at 3: BIT[3]=2.
- id4: subtract at 2: BIT[2]=2; add at 3: BIT[3]=3. So BIT[1]=1, BIT[2]=2, BIT[3]=3. Prefix sums: sum(1)=1, sum(2)=3, sum(3)=6. So distinct up to 3 =6. Query [1,3] -> sum(3)-sum(0)=6; query [2,3] -> sum(3)-sum(1)=6-1=5. Matches.
Thus correct.
Now we need to ensure the answer for each query is the number of vertices. That's it.
Now let's think about potential pitfalls with large inputs: Using dictionary for up to 300k entries is fine. Using list for last of that size.
Now we must ensure to use fast I/O: reading all ints into memory. Total integers: For each polygon, 1 + 2k_i. Sum k_i ≤ 300k, so total numbers from polygons: n (for counts) + 2 * sum k_i ≤ 1 + 2300k = 600k + n (100k) ~ 700k. Then q and 2*q numbers: up to 200k. Total around 900k integers, manageable.
Thus parse with iterator is fine.
Now implement BIT as class or functions. We'll use list and local functions to reduce overhead. But class is fine.
Potential issue: The BIT's size is n (polygons). But what if n is 100k, BIT array length 100k+2.
Now final output: print each ans on new line.
Now I think solution is ready.
But before finalizing, let's think about the property again: Is the number of vertices always equal to number of distinct edge directions? Let's double-check with a counterexample: Suppose we have two polygons, one is a triangle with vectors: (1,0), (-1,2), (0,-2). Another is a triangle with vectors: (2,0), (-2,2), (0,-2). After summing, directions: (1,0) and (2,0) same direction (1,0) after reduction, so they merge. So distinct directions are (1,0), (-1,2), (0,-2). That's 3. But can the sum have 3 vertices? The sum of two triangles is a convex hexagon? Actually Minkowski sum of two triangles is a hexagon generally if they are not degenerate. Wait typical Minkowski sum of two triangles is a hexagon, if they have three distinct edge directions each, and none of the directions coincide, you get 6 edges. But if the triangles have same set of edge directions, the sum would have 3 edges? That would be a triangle? Let's test: Two triangles with same edge directions: first triangle edges: (2,0), (-1,1), (-1,-1). Actually these sum to zero? Let's ensure each triangle is closed. If two triangles have exactly the same set of edge directions (maybe with different lengths), then the Minkowski sum will have the same set of directions, with lengths summed. But does that produce a triangle? Consider a triangle: edges: (a,b), (c,d), (e,f) such that they sum to zero. If we take another triangle with same directions but different lengths, the sum will be a polygon with those three edge vectors (scaled sum). But a set of three vectors that sum to zero always form a triangle (if they are not collinear). Indeed, three vectors with distinct directions can form a closed polygon (triangle) if they are placed head to tail. So the Minkowski sum of two triangles that are similar (same edge directions) yields a triangle (maybe larger). So number of vertices = 3 = distinct directions. So consistent.
Now consider two squares: each has 4 distinct directions, but they are the same set, so sum is a square (4 edges). So distinct =4.
Now consider two convex polygons where one has an edge direction that is exactly opposite of an edge direction from the other. That would create two opposite directions. Could the sum have a pair of opposite edges? Possibly. For instance, a rectangle (directions: (1,0),(0,1),(-1,0),(0,-1)) and a triangle with directions (1,0),(-1,1),(0,-1). Distinct: (1,0),(0,1),(-1,0),(0,-1),(-1,1). That's 5, so polygon with 5 edges. That's okay.
Now consider if the set of distinct directions does not have the property that they can be ordered cyclically with turning angles less than π? Could it be that some direction appears such that the angular order leads to a turning angle >= π? As argued, it's possible if the total lengths cause closure? Let's test: Suppose we have only two directions that are not opposite: can't close. But with multiple directions, it's possible that the angular gap between two consecutive sorted directions is > π? For example, directions at angles: 0°, 10°, 200°, 210°. Sorted: 0°,10°,200°,210°. Gaps: 10°-0°=10°, 200°-10°=190°, 210°-200°=10°, and then wrap-around: 360°-210°+0°=150°. One gap is 190° which is >180°. Is it possible for such a set to sum to zero with positive lengths? Possibly if the vectors in the two clusters balance. But would the resulting polygon be convex? For convex polygon, the external turning angles must be positive but can be as large as just under 180°. If there is a gap of 190°, that would correspond to an external turning angle of 190°, which is >180°, meaning the interior angle would be negative? Actually external turning angle is the angle you turn at each vertex when traversing the polygon in CCW order. In a convex polygon, the external angles sum to 360°, each external angle is between 0° and 180° (strictly). So no external angle can be 190°. So such a set of directions cannot correspond to a convex polygon because the edges must be arranged in CCW order with strictly increasing direction angles (mod 360°). The direction angles themselves are the edge directions. If we have a gap >180°, then when we go from one edge to the next, we would have to turn more than 180°, which would cause a concave indentation? Actually if you have a convex polygon, the edges go around the polygon, so the direction angles increase continuously, and the total increase is 360°. So the maximum increase between consecutive edges is less than 360°, but can it exceed 180°? Consider a convex polygon with very few edges: a triangle has three edges, each external turn is about 120°, which is <180°. So external turn can be up to just under 180° (if interior angle is just above 0°). So 190° is not allowed. So the set of edge directions must be such that when sorted cyclically, the maximum angular gap is <180°. Is that automatically guaranteed if the sum of vectors is zero with positive lengths? I think yes, because the polygon is convex and edges are in order, so the gaps must be <180°. But could the union of edge directions from several convex polygons produce a set where the maximum gap >= 180°? Let's think. Suppose we have three polygons: A with directions clustered around 0° (e.g., many small edges), B with directions around 180° (opposite). If we combine them, we might get two clusters opposite each other, but there would be a gap of nearly 180° between clusters? Actually between the last direction of cluster around 0° and first direction of cluster around 180°, the angular gap could be close to 180° but not exceed 180°? If clusters are exactly at 0° and 180°, the sorted order: some directions near 0°, then a big jump to near 180°, which is about 180°. Could that be exactly 180°? Possibly if there is an edge at 0° and the next at 180°, the gap is 180°. Is a turning angle of 180° allowed? That would mean the polygon turns 180°, i.e., goes straight and then reverses direction? That would cause a degenerate "spike" with interior angle 0°, which is not allowed (no three consecutive collinear, but this would be two edges with opposite directions, causing a point of zero area? Actually if you have an edge direction of (1,0) and then next edge direction of (-1,0), the external turn is 180°, which would mean the polygon goes forward then immediately backward, making a "fold". That polygon would be self-intersecting? Actually a convex polygon cannot have two consecutive edges that are opposite because that would create an interior angle of 0° (the polygon would double back). So such a configuration is impossible for a convex polygon. So the gap cannot be exactly 180°. Could it be >180°? That would be even worse. So for the Minkowski sum to be a convex polygon (as guaranteed by the problem), the set of distinct directions must have the property that the maximum angular gap < 180°. But is it always the case that the union of edge directions from convex polygons satisfies this? I think yes, because each individual polygon has that property (max gap < 180° for that polygon's edge directions). However, the union of several such sets could potentially create a larger gap? For example, polygon A has directions at 0°, 120°, 240° (equilateral triangle). Polygon B has directions at 10°, 130°, 250°. Their union includes 0°,10°,120°,130°,240°,250°. Sorted gaps: 10°,110°,10°,110°,110°,? Actually let's compute: sorted: 0°,10°,120°,130°,240°,250°. Gaps: 10°,110°,10°,110°,110°,110°? wrap: 360-250+0=110°. All gaps <=110° <180°. That's okay.
But can we create a gap >180°? Suppose we take polygon A with directions covering a small range, say between 0° and 30° (many edges), and polygon B with directions covering between 200° and 230°. Then union sorted: ... max direction from first cluster is 30°, min from second is 200°, gap = 170° (<180°). Wrap-around gap from 230° to 0° (via 360) is 130°. So still <180°. To get gap >=180°, the clusters would need to be separated by at least 180°, and also the wrap-around cluster must be small. But the total angular coverage of each polygon individually is 360° (since they are closed convex polygons). Actually a convex polygon's edge directions cover the full circle? No, they cover the full circle: as you go around, the edge direction rotates by exactly 360°. That means the set of edge directions, when considered as angles modulo 360°, is not necessarily covering all angles; there are gaps. But the total rotation is 360°, so the sum of gaps equals 360°. Each gap is positive, but any individual gap could be larger than 180°? Let's see: In a convex polygon, the exterior turning angle at each vertex is positive and sum to 360°. Could one exterior angle be >180°? That would correspond to interior angle <0°, which is impossible for convex polygon (interior angles are between 0° and 180°, strictly between 0 and 180 due to no three collinear). So each turning angle (gap between edge directions) is strictly between 0° and 180°. So for any convex polygon, the maximum angular gap between consecutive edge directions (in sorted order) is <180°. This is a property: The polygon is convex iff the sequence of edge direction angles is strictly increasing and the difference between consecutive angles is less than π (180°) when taken modulo 2π. So each polygon's own set of directions has the property that all gaps are <180°.
Now consider the union of sets from multiple polygons. Could the union have a gap >=180°? That would mean there is an angular interval of size at least 180° that contains no edge direction from any polygon in the set. But each polygon individually covers the full circle with its edge directions? Actually no, each polygon's directions are discrete; they don't cover the whole circle, they have gaps. But the crucial point: Because each polygon is closed and convex, the sum of its edge vectors is zero. This imposes that the edge direction vectors, when weighted by their lengths, sum to zero. This implies that the directions cannot all lie within a half-plane; they must span more than 180°. However, it's possible that a single polygon has all its directions within a half-plane? No, because if all edge vectors lie within a half-plane, their sum would be nonzero (pointing within that half-plane). So any convex polygon's edge directions must cover more than 180° of the circle; i.e., the angular span (max-min) is >180° (strictly). Actually for a closed polygon, the set of edge vectors must positively span the origin. This means that the convex cone generated by the edge vectors must be the whole plane? More precisely, the condition for a set of vectors with positive weights to sum to zero is that they are not all contained in any open half-plane (by the separating hyperplane theorem). So for a convex polygon, the edge vectors (all pointing around) satisfy that there is no line through origin such that all vectors lie strictly on one side. Equivalently, the angular range (the smallest arc containing all directions) must be at least 180°? Actually if they all lie within a closed half-plane (≤180°), the sum could still be zero if they exactly balance? Let's consider three vectors: two at angle 0° (positive x) with length 1, one at angle 180° (negative x) with length 2. They all lie on a line (half-plane is the line? Actually they are within a 180° closed half-plane (the x-axis). Their sum is zero? 1+1-2=0. So yes, they can sum to zero while being within a half-plane (even collinear). But would such a set correspond to a convex polygon? A set of three vectors that are collinear (two in one direction, one opposite) cannot form a closed polygon with non-zero area because they would all be on the same line, resulting in a degenerate polygon (a line segment traversed back and forth). But convex polygon with area >0 must have edges not all in a half-plane? Actually a convex polygon with non-zero area must have edges that span at least two dimensions; they cannot all be within a half-plane of less than 180°? Wait, if all edge vectors are within a closed half-plane of angle <= 180°, it's possible they still span the plane? For example, a triangle with angles 30°, 150°, 180°? No. Let's think: For a polygon to have area, the edge vectors must not all be contained in a half-plane that is less than 180°? Actually consider a very thin triangle: angles almost 0°, 90°, 90°? Not sure. The necessary and sufficient condition for a set of vectors with positive lengths to form a closed polygon (non-self-intersecting) when placed head-to-tail in order of increasing angle is that the angles are increasing and the turning angles sum to 360°. This already ensures that the maximum gap between consecutive angles is less than 180°, because if a gap >=180°, the polygon would be non-convex or self-intersecting. So if we take the union of several polygons' edge directions, could the combined set have a gap >=180°? Suppose we have two polygons: one's edge directions are all in the range [0°, 179°] (i.e., spanning 179°), and the other's edge directions are all in the range [181°, 360°] (spanning 179°). The union might have a gap from 179° to 181° = 2°, which is small. That's not >=180°. To have a gap >=180°, we would need that all edge directions from all polygons lie within an arc of less than 180°, leaving the complementary arc of more than 180° empty. But as argued, each individual polygon's edge directions cannot all lie within a half-plane of less than 180°? Actually they could lie within a half-plane? Let's test with a triangle: vertices (0,0), (10,0), (0,1). Edge vectors: (10,0) angle 0°, (-10,1) angle ~174.3°, (0,-1) angle 270° (or -90°). That's not all within a 180° half-plane? The vectors are at 0°, 174°, and 270°. The smallest arc containing them is from 270° around to 0° through 360°: that's 90°? Actually angles: 0°, 174°, 270°. Represent them modulo 360: sort: 0°, 174°, 270°. The arc from 270° to 360° then to 0°? That's 90°? Actually the complement arc from 270° to 360° is 90°, plus 0°? The maximal gap is from 174° to 270° = 96°, and from 270° to 360°+0° = 90°. So all vectors are within an arc of 270°? The smallest arc that contains all points is actually the arc from 270° around to 0° through 360°, which is 90°? Wait: The set of points on a circle: {0°,174°,270°}. The smallest arc covering them is not necessarily containing the wrap-around? Usually the arc is defined without wrap, but we can consider the circular order. The minimal arc length that contains all points is the complement of the maximum gap. The maximum gap is from 174° to 270° = 96°, so the minimal covering arc is 360° - 96° = 264°. So they are contained within a 264° arc, which is >180°. So they are not contained in any half-plane (180°). Actually a half-plane corresponds to an arc of length 180° (closed). 264° > 180°, so it's not contained in a half-plane. So each convex polygon's edge directions are not contained in any open half-plane; the minimal arc containing them is >180°. Indeed, for a closed convex polygon, the outward normals cover full circle; but edge directions also cover more than 180°? Let's examine a degenerate convex polygon like a line segment? But polygon must have area? Convex polygon can be degenerate? Typically polygon with area >0, yes. The problem says convex polygons; they may be degenerate? Usually convex polygon with at least 3 vertices implies non-zero area? Not necessarily if all points collinear, but that violates no three consecutive collinear, so they are not collinear, so area >0. So edge directions must span at least two dimensions, and the condition that the polygon is closed implies the vector sum is zero. This condition ensures that the edge vectors positively span the plane, meaning that the origin is in the interior of the convex cone generated by the edge vectors? Actually for a convex polygon, the edge vectors (as free vectors) when placed tail at origin, the endpoints (the vectors) are all pointing around. The condition for closure is that the weighted sum is zero, which implies that the vectors are not all contained in a closed half-plane (unless some are exactly opposite and cancel). But could a convex polygon have edge vectors that all lie within a closed half-plane? Consider a triangle with vertices (0,0), (10,0), (5,1). Edge vectors: (10,0) angle 0°, (-5,1) angle ~168.7°, (-5,-1) angle ~191.3°. That's angles 0°, 168.7°, 191.3°. The set is not contained in any half-plane of 180°? The half-plane from angle 90° to 270° (the left half) contains 168.7°,191.3° but not 0°. The half-plane from angle -90° to 90° (right half) contains 0°,168.7°? 168.7° is not within -90° to 90° (which is 0° to 90° and 270° to 360°)? Actually half-plane of width 180° can be oriented arbitrarily. Try an orientation centered at 0°: half-plane from -90° to 90° contains angles 0° and 168.7°? 168.7° is >90°, so no. Try orientation centered at 180°: half-plane from 90° to 270° contains 168.7°,191.3°, but not 0°. So no single closed half-plane of exactly 180° contains all three. However, an open half-plane of >180° could. So indeed the edge directions of a convex polygon always span more than 180°, i.e., the minimal arc containing them is >180°. This property implies that for any convex polygon, the maximum gap between consecutive edge directions (sorted) is <180° because total sum of gaps = 360°, and if one gap >=180°, then the sum of the remaining gaps <=180°, so the directions would be contained in an arc of size <=180° (the complement of the big gap). That would mean they all lie within a half-plane, contradicting the property that they span more than 180°. So indeed each convex polygon has max gap <180°.
Now, does the union of multiple such sets maintain max gap <180°? Possibly the union could have a larger gap than any individual. For instance, if we have polygon A with directions in arcs covering [0°, 170°] and [350°, 360°] (so max gap maybe 180°? Actually if it covers [0,170] and [350,360], the max gap is from 170° to 350° = 180°. But can a convex polygon have such a gap of exactly 180°? As argued, max gap must be <180°, so cannot be exactly 180°. So each polygon's max gap is strictly less than 180°. So for polygon A, the uncovered arc is less than 180°. For polygon B, suppose its directions lie in arcs that are disjoint from the gap of A, maybe covering the missing region. But could the union still have a gap >=180°? Consider polygon A with directions covering [0°, 179°] (max gap from 179° to 360°? Actually if it covers up to 179°, the gap from 179° to 360° is 181°, but can it cover up to 179°? The max gap of A must be <180°, so the uncovered arc is <180°, meaning that the complement of the convex hull of its directions (the largest gap) is <180°. That means the set of directions is not contained in any half-plane, so the minimal arc covering them is >180°, which implies that the largest gap is <180°. So for A, the largest gap <180°, so there is no uncovered arc >=180°. Similarly for B. Now the union of A and B: could the largest gap become larger than the individual gaps? Suppose A's directions cover most of the circle but leave a small gap of size g_A < 180°, and B's directions also cover most but leave a gap of size g_B < 180°. If the gaps happen to align (i.e., both have a gap in the same angular region), then the union might still have that gap (the intersection of the gaps) but the size would be less than both (since intersection smaller). If the gaps are in different places, the union might cover all, reducing the overall gap. So the union's largest gap cannot exceed the maximum of the individual gaps? Actually if A has a gap of size g_A, B has a gap of size g_B, and these gaps are disjoint, the union might have a gap that is the intersection? Let's reason: The union's gap is an angular interval that contains no direction from either A or B. This gap must be a subset of some gap of A and also a subset of some gap of B? Actually if an interval contains no A directions and no B directions, then it must be contained in a gap of A and also contained in a gap of B. So the union's gaps are intersections of gaps from A and B. So the size of any union gap is at most min(size of some A gap, size of some B gap) if they overlap, or possibly zero if they don't overlap. So the maximum gap of the union is at most the maximum of the minima? Actually, for a gap to exist in the union, there must be an interval that lies in a gap of A and also in a gap of B. Thus the size of any union gap is ≤ the size of the smaller of the two gaps it lies in. Since each individual gap < 180°, the union's gaps are also < 180°. Therefore, the union of multiple convex polygons' edge direction sets will also have max gap < 180°. So the resulting set of distinct directions can always be arranged as a convex polygon (the Minkowski sum) and the number of vertices equals the number of distinct directions. So our answer is correct.
Thus the problem reduces to distinct count queries.
Now we need to implement and ensure no mistakes.
Potential issue: The total number of distinct directions could be up to 300k, which is fine.
Now we should also consider memory: storing poly_edges as list of lists of ints. Each edge id is an int (4 bytes?). Python ints are larger, but 300k of them is okay.
Now I'd like to test with some random data using a separate script, but given time, trust reasoning.
Now consider edge case: n=100000, each polygon has 3 vertices (minimum). total edges=300k. q=100k. Running time: 300k updates * (2 BIT ops) = 600k BIT updates, each O(log n) ~ 17 steps, ~10 million bit index operations. Plus dictionary lookups ~300k. Python can handle within 2-3 seconds? Usually 10 million simple operations may be borderline but with optimized loops and local variables it's fine.
But we need to be careful about recursion limit? Not relevant.
We also need to import math.
Now one more nuance: The reduction of vectors via gcd may produce negative zero? Not an issue.
Now code.
Pseudo:
import sys, math
def main(): data = list(map(int, sys.stdin.buffer.read().split())) it = iter(data) n = next(it) poly_edges = [] dir_to_id = {} for _ in range(n): k = next(it) pts = [(next(it), next(it)) for __ in range(k)] edge_ids = [] for j in range(k): x1, y1 = pts[j] x2, y2 = pts[(j+1)%k] dx = x2 - x1 dy = y2 - y1 g = math.gcd(abs(dx), abs(dy)) # g>0 dx //= g dy //= g key = (dx, dy) if key in dir_to_id: cid = dir_to_id[key] else: cid = len(dir_to_id) + 1 dir_to_id[key] = cid edge_ids.append(cid) poly_edges.append(edge_ids) q = next(it) queries_by_r = [[] for _ in range(n+1)] for qi in range(q): l = next(it); r = next(it) queries_by_r[r].append((l, qi)) # BIT class BIT: slots = ('n','bit') def init(self, n): self.n = n self.bit = [0](n+2) def add(self, i, delta): bit = self.bit n = self.n while i <= n: bit[i] += delta i += i & -i def sum(self, i): s = 0 bit = self.bit while i>0: s += bit[i] i -= i & -i return s bit = BIT(n) last = [0](len(dir_to_id)+2) # 1-indexed ids ans = [0]*q for i in range(1, n+1): for cid in poly_edges[i-1]: prev = last[cid] if prev != 0: bit.add(prev, -1) bit.add(i, 1) last[cid] = i for l, idx in queries_by_r[i]: ans[idx] = bit.sum(i) - bit.sum(l-1) out = '\n'.join(map(str, ans)) sys.stdout.write(out)
if name == 'main': main()
Now test with given sample.
We'll run mental simulation; seems fine.
Now I'd like to check for potential off-by-one: poly_edges indexed 0, i from 1 to n inclusive, poly_edges[i-1] gives edges of polygon i.
Now, in BIT, we added up to n, so bit.n = n, fine.
Now about the last array: size distinct_count+2 to avoid index error (since ids start at 1, we need up to max_id). We allocate len(dir_to_id)+2.
Now, possible issue: The BIT sum(l-1) when l=1 => sum(0) returns 0.
Now all good.
Now let's double-check with a more complex scenario: n=2, polygon1: square (4 edges), polygon2: triangle (3 edges) with all distinct directions from square? Suppose square: (1,0),(0,1),(-1,0),(0,-1). Triangle: (2,0),(-1,1),(-1,-1). Directions: square: (1,0),(0,1),(-1,0),(0,-1). Triangle: (1,0) after reduction (since (2,0)->(1,0)), (-1,1), (-1,-1). Union: (1,0),(0,1),(-1,0),(0,-1),(-1,1),(-1,-1). That's 6. Query [1,2] ->6.
Our algorithm: Process poly1: add 4 distinct at index1. After poly1, BIT sum1=4. Process poly2: for each edge:
- (1,0): prev=1 -> subtract at1, add at2.
- (-1,1): new -> add at2.
- (-1,-1): new -> add at2. Also (from triangle) there is also (-1,1) and (-1,-1) only one each. So after updates, BIT: index1=4-1=3, index2=3 (since three adds? Actually also need to consider that triangle also has (1,0),(-1,1),(-1,-1). So we did subtract at1 for (1,0) then add at2 for (1,0); then add at2 for (-1,1); add at2 for (-1,-1). So BIT[1] becomes 3, BIT[2] becomes 3. So sum(2)=6. Works.
Now if triangle had an edge direction already in square (like (0,1)), then distinct would be 5. Process would subtract at1 for that direction and add at2, etc. So BIT[1] would be 3, BIT[2]=2? Actually after square: 4 at index1. Then triangle: (1,0) subtract at1-> BIT[1]=3, add at2-> BIT[2]=1; (0,1) subtract at1-> BIT[1]=2, add at2-> BIT[2]=2; ( -1, -1 ) new-> add at2-> BIT[2]=3. So sum(2)=2+3=5. Works.
Now, what if a polygon has multiple edges with same direction (shouldn't happen). But if it does, our algorithm still yields correct distinct count as argued. So no issue.
Now we should also consider that the total number of distinct directions could be up to 300k, and last array of that size is fine.
Now we need to ensure that reading input with iter over list of ints is okay memory-wise.
One more nuance: The problem statement says "The sum of Minkowski of p polygons (p > 2), you need to calculate the sum of Minkowski of the first p - 1 polygons, and then calculate the sum of Minkowski of the resulting polygon and the p-th polygon." This indicates an order of summation, but as we know Minkowski sum is associative and commutative, so order doesn't matter.
Now, check sample: Yes.
Now potential pitfalls: The convex polygons could be given with vertices in CCW order, but we must ensure we compute edges correctly (closing from last to first). Done.
Now about integer overflow: Not in Python.
Now final code as above.
Now I'll write final answer.
But before finalizing, let's think about if there is any possibility that the Minkowski sum could have fewer vertices than the number of distinct directions due to some direction's total length being zero? That would require that the sum of lengths from all polygons in that direction is zero. Since each edge length is positive, that can only happen if no polygon has that direction. So distinct directions present all have positive length. So okay.
Now any nuance about degenerate polygons where some edge length is zero? Not allowed because vertices are distinct and no three consecutive collinear, so edges have non-zero length.
Thus final solution is correct.
Now produce final answer.
But wait, there's an alternative approach: Use segment tree to combine sets of directions? But offline BIT is simpler.
Now we should also consider that the problem might have large memory for storing poly_edges. 300k integers, each Python int ~28 bytes, so ~8.4 MB, plus list overhead. Acceptable.
Now ensure we use slots for BIT maybe not needed.
Now finalize.
One more thought: Could there be an issue with the number of vertices being counted as distinct edge directions, but is it always equal? Let's test with a simple example: Two identical squares, but one rotated by 45 degrees? Square rotated 45° is a diamond: edges directions: (1,1), (-1,1), (-1,-1), (1,-1). Distinct union with axis-aligned square: (1,0),(0,1),(-1,0),(0,-1),(1,1),(-1,1),(-1,-1),(1,-1) -> 8 directions. So sum should have 8 vertices (i.e., an 8-gon). Indeed, Minkowski sum of a square and a diamond (both convex quadrilaterals) is an octagon. So correct.
Now what about sum of three squares? If all axis-aligned, same directions, distinct =4. So sum is a square. Works.
Thus confident.
Now implement final solution.
Edge Cases: n=1, q=1, l=r=1. We compute poly_edges[0] list of k ids. Process i=1: for each edge, add. BIT after processing: last set to 1, BIT[1]=k. Query after: ans = BIT.sum(1)-BIT.sum(0)=k. Output k. Good.
Now final code.
But we must be cautious about reading all ints: Use next(it) repeatedly; we need to handle StopIteration? Not needed because input correct.
Now let's write final answer in the required format.
Potential micro-optimizations: Use local variable references inside loops for bit.add, bit.sum, last, poly_edges_i. But not necessary.
Now final answer.
I'll now produce final solution explanation and code. ```python import sys import math
def main() -> None: data = list(map(int, sys.stdin.buffer.read().split())) it = iter(data)
n = next(it) polygons = [] # list of lists of direction ids for each polygon dir_to_id = {} # mapping (dx, dy) -> unique id (starting from 1) for _ in range(n): k = next(it) pts = [(next(it), next(it)) for __ in range(k)] edge_ids = [] for j in range(k): x1, y1 = pts[j] x2, y2 = pts[(j + 1) % k] dx = x2 - x1 dy = y2 - y1 g = math.gcd(abs(dx), abs(dy)) dx //= g dy //= g key = (dx, dy) cid = dir_to_id.get(key) if cid is None: cid = len(dir_to_id) + 1 dir_to_id[key] = cid edge_ids.append(cid) polygons.append(edge_ids) q = next(it) queries_by_r = [[] for _ in range(n + 1)] for idx in range(q): l = next(it) r = next(it) queries_by_r[r].append((l, idx)) # Fenwick tree (Binary Indexed Tree) class BIT: __slots__ = ('n', 'bit') def __init__(self, n: int): self.n = n self.bit = [0] * (n + 2) def add(self, i: int, delta: int) -> None: n = self.n bit = self.bit while i <= n: bit[i] += delta i += i & -i def sum(self, i: int) -> int: s = 0 bit = self.bit while i: s += bit[i] i -= i & -i return s bit = BIT(n) last = [0] * (len(dir_to_id) + 2) # last occurrence of each direction (0 = none) answers = [0] * q for i in range(1, n + 1): for cid in polygons[i - 1]: prev = last[cid] if prev != 0: bit.add(prev, -1) bit.add(i, 1) last[cid] = i for l, idx in queries_by_r[i]: answers[idx] = bit.sum(i) - bit.sum(l - 1) sys.stdout.write('\n'.join(map(str, answers)))if name == 'main': main()