2298. How Many Polygons Contain the Point
k simple polygons are given. For each query point print how many of them
contain it. A point ON a polygon's boundary counts as contained by that polygon.
two squares (0,0)-(6,6) and (3,3)-(9,9)
(1,1) -> 1 only the first
(4,4) -> 2 both
(7,7) -> 1 only the second
(0,0) -> 1 a vertex of the first, which counts
## The rule that has to be settled first
"Contains" has to say what happens on the boundary, and here the boundary
counts. That choice is not cosmetic. With k polygons sharing edges, a point on
a shared edge is contained by both under this rule and by neither under the
strict one, so the answer differs by two. The declared tests include a point on
a shared edge for exactly that reason.
## What most people try first
A strict interior test, because point-in-polygon is usually phrased that way.
With the rule above, ON has to be folded in with IN, which means the
boundary test cannot be skipped: it is not an edge case to ignore but half the
answer.
The second instinct is to use a bounding box as the test rather than as a filter. A point inside a polygon's bounding box need not be inside the polygon, which the concave polygon in the declared tests shows.
## What to do
For each polygon and each query, run the exact two-stage containment test:
stage 1 is the point on any closed edge? if yes, contained
stage 2 count rightward ray crossings with the
half-open rule; odd means contained
Add one for each polygon that says yes. Both stages are integer-only: the first
is a cross product compared with zero plus a bounding-box check, the second is a
pair of products compared in an order the sign of y2 - y1 decides.
A bounding-box pre-test per polygon is a legitimate speed-up, because a point outside the box is certainly outside the polygon. It is a filter and never an answer: the implication only runs one way.
## Cost
O(total vertices) per query, so O(V * q) with V the total number of
vertices over all polygons. At V up to 2000 and q up to 1000 that is
2 * 10^6 edge visits, which is the intended cost.
## Width
Coordinates satisfy |x|, |y| <= 1000000, so each difference is at most 2 * 10^6 and each cross product at most 8 * 10^12 in magnitude. A signed 32-bit integer stops at 2147483647, so a 32-bit cross product wraps and reports the wrong SIDE, which flips a containment answer rather than merely shifting a number. The value is below 2^53 = 9007199254740992, so a JavaScript Number is exact and no BigInt is needed; the bitwise operators must not appear, because they coerce to 32 bits.
Constraints - `1 <= k <= 50` - `3 <= m <= 1000` for each polygon - the total number of vertices over all polygons is at most 2000 - `1 <= q <= 1000` - `-1000000 <= x, y <= 1000000` - every polygon is simple, with its vertices in order around the boundary in either direction - polygons may overlap, be nested, or be given more than once
Input
The first line contains an integer k, the number of polygons.
Then k polygons follow. Each is given as a line containing an integer m, the number of its vertices, followed by m lines each containing two integers x y, that polygon's vertices in order around its boundary.
After the polygons comes a line containing an integer q.
Each of the next q lines contains two integers x y, one query point.
Output
For each query print one integer on its own line, the number of polygons that contain the point, counting a polygon whose boundary passes through the point, with nothing else on the line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.