8555: CGL_3_C : Polygon-Point-Containment
[Creator : ]
Description
For a given polygon $g$ and target points t, print "2" if g contains t, "1" if t is on a segment of g, "0" otherwise.
$g$ is represented by a sequence of points $p_1, p_2,..., p_n$ where line segments connecting $p_i$ and $p_{i+1}\ (1 ≤ i ≤ n−1)$ are sides of the polygon. The line segment connecting $p_n$ and $p_1$ is also a side of the polygon.
Note that the polygon is not necessarily convex.
$g$ is represented by a sequence of points $p_1, p_2,..., p_n$ where line segments connecting $p_i$ and $p_{i+1}\ (1 ≤ i ≤ n−1)$ are sides of the polygon. The line segment connecting $p_n$ and $p_1$ is also a side of the polygon.
Note that the polygon is not necessarily convex.
Input
The entire input looks like:
$g$(the sequence of the points of the polygon)
$q$(the number of queris = the number of target points)
1st query
2nd query
$\vdots$
qth query
$g$ is given by coordinates of the points $p_1,..., p_n$ in the following format:
$n$
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$x_n\ y_n$
The first integer $n$ is the number of points.
The coordinate of a point $p_i$ is given by two integers $x_i$ and $y_i$. The coordinates of points are given in the order of counter-clockwise visit of them.
Each query consists of the coordinate of a target point $t$. The coordinate is given by two intgers $x$ and $y$.
$g$(the sequence of the points of the polygon)
$q$(the number of queris = the number of target points)
1st query
2nd query
$\vdots$
qth query
$g$ is given by coordinates of the points $p_1,..., p_n$ in the following format:
$n$
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$x_n\ y_n$
The first integer $n$ is the number of points.
The coordinate of a point $p_i$ is given by two integers $x_i$ and $y_i$. The coordinates of points are given in the order of counter-clockwise visit of them.
Each query consists of the coordinate of a target point $t$. The coordinate is given by two intgers $x$ and $y$.
Output
For each query, print "2", "1" or "0".
Constraints
$3 ≤ n ≤ 100$
$1 ≤ q ≤ 1000$
$-10000 ≤ x_i, y_i ≤ 10000$
No point of the polygon will occur more than once.
Two sides of the polygon can intersect only at a common endpoint.
$1 ≤ q ≤ 1000$
$-10000 ≤ x_i, y_i ≤ 10000$
No point of the polygon will occur more than once.
Two sides of the polygon can intersect only at a common endpoint.
Sample 1 Input
4
0 0
3 1
2 3
0 3
3
2 1
0 2
3 2
Sample 1 Output
2
1
0