2295. Does the Polygon Contain the Point

A simple polygon is given by its n vertices in order. For each query point print IN if it is strictly inside, ON if it is on the boundary, and OUT if it is strictly outside.

square (0,0) (6,0) (6,6) (0,6) (3,3) -> IN (7,3) -> OUT (0,0) -> ON (3,0) -> ON

## What most people try first

Counting ray crossings and reporting the parity, with nothing else. That answers IN or OUT, and on the boundary it answers whichever of the two the tie-breaking rule happens to produce. Since a point on an edge is neither strictly inside nor strictly outside, no crossing rule can be relied on there: the rule was designed to make the INTERIOR come out right, and it does that by deciding boundary-adjacent cases consistently rather than correctly.

## So test the boundary first, exactly, and then count

Two stages, in this order.

Stage one. For each edge from u to v, the point is on it when cross(u, v, p) == 0 and p lies inside the smallest axis-aligned box containing u and v. If any edge says yes, print ON and stop. This is exact, so there is nothing left to tie-break.

Stage two. The point is now known to be off the boundary, so shoot a ray in the +x direction and count the edges it crosses, with the half-open rule:

count the edge <-> exactly one of y1 > py and y2 > py holds and (px - x1) * (y2 - y1) compares with (py - y1) * (x2 - x1) the way (y2 > y1) says

Odd means IN, even means OUT.

## Why the parity argument is valid

Walk from the query point out to infinity along the ray. The ray ends outside, because the polygon is bounded. Every time it crosses the boundary it swaps between inside and outside, and the half-open rule guarantees each crossing is counted exactly once even when the ray passes through a vertex. So the number of swaps has the same parity as "started inside", which is what the count reports. The argument needs the polygon to be SIMPLE: a self-crossing path can wind twice and then parity says nothing, which is why a winding number is the right tool there and not a parity.

## The two orderings that are wrong

Counting first and treating the boundary as a special case of the count: the count is not reliable there, so the special case has nothing to attach to.

Testing the boundary with a tolerance instead of exactly: the whole reason the cross product is used is that == 0 is a decidable question about integers. A tolerance reintroduces the problem it solves.

## Cost

O(n) per query, O(n * q) overall, at most 10^6 edge visits here. For a CONVEX polygon the same question can be answered in O(log n), which is the next problem.

## 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 - `3 <= n <= 1000` - `1 <= q <= 1000` - `-1000000 <= x, y <= 1000000` - the polygon is simple, and its vertices are given in order around the boundary in either direction - a query point may be a vertex, may be on an edge, or may be anywhere else