How many laps

polygon points maps and navigation contests

A runner recorded a training session: three laps around the city, each from Republic Square along the shortest streets through several landmarks and back. The track is a closed polyline that crosses itself, in places goes along the same street twice and in both directions. The coach wants to know, for each point on the map, how many times the runner went around it. Going around anticlockwise counts as +1, clockwise as −1, so a lap there and a lap back add up to zero.

The second test is such a session on the streets of Almaty from OpenStreetMap, in integer metres on the grid of this catalogue’s road map; the points are landmarks and crossings the track does not pass through.

Input

The first line holds the number of track vertices n (3 ≤ n ≤ 2000), then n lines with coordinates x y in order of movement; after the last vertex the runner returns to the first. Neighbouring vertices are distinct, but otherwise the track may do anything: cross itself, pass through the same points, go along segments already covered. Then the number of points q (1 ≤ q ≤ 1000) and q lines with their coordinates. No point lies on the track. All coordinates are integers, |x|, |y| ≤ 10⁹.

Output

For each point on a line of its own, an integer: how many times the track goes around it anticlockwise minus the times clockwise.

Examples

Example 1

Input

Output

Limits

Time · Python: 6000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Imagine you stand at the point and turn to face the runner while they run along the track. By how many full turns will you have rotated by the end of the session? That is the answer, the winding number of the track around the point.

2Hint 2

Adding up angles with atan2 is possible, but there is a way without trigonometry. Draw a ray east from the point. Each time the track crosses the ray going up, you turn through east anticlockwise; going down, clockwise.

3The idea

The winding number equals a sum over the crossings of the ray: +1 for a segment crossing the ray from below upwards, −1 from above downwards. The parity of this sum is the ordinary ray test for “inside or outside”; the sum itself knows more: how many times and in which direction.

4Walkthrough

For a segment A → B and a point P compute s = cross(A, B, P). The segment goes up across the ray if A_y ≤ P_y < B_y; the crossing is east of the point if the point is to the left of the segment, s > 0. Then +1. The segment goes down if B_y ≤ P_y < A_y, and the crossing is to the east if the point is to the right, s < 0. Then −1.

Why this is the winding number. The direction from the point to the runner passes through east exactly when the runner crosses the ray. If they cross it moving up, the direction turns anticlockwise; if down, clockwise. Every full turn passes through east once, so the sum of ±1 over the crossings is the signed number of full turns. Half-open inequalities (one bound with “≤”, the other with “<”) settle the case where the ray passes through a vertex of the track: of the two segments at the vertex at most one is counted, and only if the track passes through the ray right across. Segments covered again do not get in the way: there and back along the same street give +1 and −1.

This is how filling by the nonzero rule is computed in SVG and on the browser canvas: a point is filled if its winding number is not zero.

4+Solution

5Complexity

O(n) per point, O(nq) in all: two million segment checks in the worst case, all in integers.

6Common mistakes

Parity instead of the sum. The test “the ray crossed the boundary an odd number of times” answers only 0 or 1 and loses the sign. This is the wrong solution of the problem: in the spiral of the third test points near the centre are gone around 450 times.
Crossings without sign. Counting all crossings of the ray and dividing by two is wrong: a lap clockwise and a lap anticlockwise together give zero, not two.
Angles in double. The sum of angles via atan2 is right if rounded to a whole number of turns at the end, but it is trigonometry on every segment, and for points right next to the track the error grows. The signs of crossings give the same answer in integers.
Segment ends included on both sides. A ray through a vertex where the track passes right across is then counted twice.

Algorithms behind it

GEO Algorithm Point in polygon A ray from the point crosses the boundary an odd number of times: the point is inside; the winding number is the same with signs. O(n) per point 2 problems GEO Technique Vectors and orientation The sign of the cross product is a left or right turn; almost all of computational geometry stands on it. O(1) per turn 2 problems