2297. The Winding Number of a Closed Path

A closed path visits n points in order and returns to the first. The path may cross itself and may repeat points. For each query point print ON_PATH if the point lies on the path, and otherwise print the WINDING NUMBER: how many times the path travels anticlockwise around the point, counting a clockwise loop as minus one.

square (0,0) (6,0) (6,6) (0,6) at (3,3) -> 1 the same square listed clockwise at (3,3) -> -1 the square traced twice round at (3,3) -> 2 a figure of eight, loops opposite ways at either centre -> 1 and -1 any point outside any closed path -> 0

## What most people try first

A parity count of ray crossings, which is the point-in-polygon answer. It is the wrong tool twice over. It gives only 0 or 1, so it can never report 2 or -1, and it is justified by an argument that assumes the path is SIMPLE. On a path that winds twice, the ray crosses the boundary twice, parity says outside, and the point is very much enclosed.

The other instinct is to add up the turning angles and divide by a full turn. That is the definition, and it needs an arctangent per edge, so the answer arrives as a floating-point number near an integer and has to be rounded. For a point very close to the path the sum of angles is a sum of nearly cancelling quantities, which is where floating point is at its worst.

## Counting signed crossings instead

The winding number equals the number of times the path crosses a ray, counted with a sign. Take the ray going right from the query point. An edge that crosses it UPWARD, passing the query's height from below to above, contributes +1 if the query point is to the LEFT of that edge. An edge crossing DOWNWARD contributes -1 if the query point is to the RIGHT. Left and right come from the sign of a cross product, so the whole computation is integers.

w = 0 for each edge a -> b if a.y <= py: if b.y > py and cross(a, b, p) > 0: w += 1 else: if b.y <= py and cross(a, b, p) < 0: w -= 1

Two details carry the correctness. The height comparison is asymmetric, <= on one side and > on the other, which makes each edge's y span half open so a vertex at the query's height is counted for exactly one of its two edges. And the cross-product test is what restricts the count to the crossings on the RIGHT-hand ray rather than all crossings of the horizontal line.

## The boundary, settled

A point on the path has no winding number: the path passes through it, so no number of turns around it is defined. The answer there is the word ON_PATH, and it is decided first, exactly, by testing the point against every closed edge with the cross product and the bounding box. Deciding it first matters because the crossing count returns some number for such a point, and that number means nothing.

A zero-length edge, which a repeated point produces, contributes nothing: both height tests cannot disagree when the two endpoints have the same y. The closing edge from the last point back to the first is part of the path and must be included.

## 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.

The winding number itself is bounded by n / 2, so it is small; what needs the wide type is the cross product inside the test.

Constraints - `3 <= n <= 1000` - `1 <= q <= 1000` - `-1000000 <= x, y <= 1000000` - the path may cross itself, and consecutive points may coincide, making a zero-length edge - the path closes from the last point back to the first