Problem:


Polygon-Point-Containment

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 p1, p2,..., pn where line segments connecting pi and pi+1 (1 ≤ i ≤ n-1) are sides of the polygon. The line segment connecting pn and p1 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
:
qth query

g is given by coordinates of the points p1,..., pn in the following format:

n
x1 y1 
x2 y2
:
xn yn

The first integer n is the number of points. The coordinate of a point pi is given by two integers xi and yi. 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 ≤ xi, yi ≤ 10000

No point of the polygon will occur more than once.

Two sides of the polygon can intersect only at a common endpoint.

Sample Input

4
0 0
3 1
2 3
0 3
3
2 1
0 2
3 2

Sample Output

2
1
0



Sample input:
4
0 0
3 1
2 3
0 3
3
2 1
0 2
3 2


Sample output:
2
1
0

Submission status: Wrong Answer

Solution code:
import math


def dot(ux, uy, vx, vy):
    return ux*vx + uy*vy


def cross(ux, uy, vx, vy):
    return ux*vy - uy*vx


def dist_to_segment(x, y, ax, ay, bx, by):
    if dot(x - ax, y - ay, bx - ax, by - ay) < 0:
        return math.hypot(x - ax, y - ay)
    if dot(x - bx, y - by, ax - bx, ay - by) < 0:
        return math.hypot(x - bx, y - by)
    c = abs(cross(bx - ax, by - ay, x - ax, y - ay))
    return c / math.hypot(bx - ax, by - ay)


n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
g.append(g[0])

q = int(input())
for _ in range(q):
    x, y = map(int, input().split())
    i_min, d_min = 0, 1e7
    for i in range(n):
        x1, y1 = g[i]
        x2, y2 = g[i + 1]
        d = dist_to_segment(x, y, x1, y1, x2, y2)
        if d < d_min:
            i_min, d_min = i, d

    x1, y1 = g[i_min]
    x2, y2 = g[i_min + 1]
    print(cross(x1 - x, y1 - y, x2 - x, y2 - y) + 1)

Submission status: Wrong Answer

Solution code:
import math


def dot(ux, uy, vx, vy):
    return ux*vx + uy*vy


def cross(ux, uy, vx, vy):
    return ux*vy - uy*vx


def dist_to_segment(x, y, ax, ay, bx, by):
    if dot(x - ax, y - ay, bx - ax, by - ay) < 0:
        return math.hypot(x - ax, y - ay)
    if dot(x - bx, y - by, ax - bx, ay - by) < 0:
        return math.hypot(x - bx, y - by)
    c = abs(cross(bx - ax, by - ay, x - ax, y - ay))
    return c / math.hypot(bx - ax, by - ay)


n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
g.append(g[0])

q = int(input())
for _ in range(q):
    x, y = map(int, input().split())
    i_min, d_min = 0, 1e7
    for i in range(n):
        x1, y1 = g[i]
        x2, y2 = g[i + 1]
        d = dist_to_segment(x, y, x1, y1, x2, y2)
        if d < d_min:
            i_min, d_min = i, d

    x1, y1 = g[i_min]
    x2, y2 = g[i_min + 1]

    if cross(x1 - x, y1 - y, x2 - x, y2 - y) > 0:
        print(2)
    elif dist_to_segment(x, y, x1, y1, x2, y2) > 0:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math

EPS = 1e-10

class Vector:
    def __init__(self, x=None, y=None):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vector(self.x - other.x, self.y - other.y)

    # can't  apply "number * Vector" but "Vector * number"
    def __mul__(self, k):
        return Vector(self.x * k, self.y * k)

    def __truediv__(self, k):
        return Vector(self.x / k, self.y / k)

    def __gt__(self, other):
        return self.x > other.x and self.y > other.yb

    def __lt__(self, other):
        return self.x < other.x and self.y < other.yb

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    # usually cross operation return Vector but it returns scalor
    def cross(self, other):
        return self.x * other.y - self.y * other.x

    def norm(self):
        return self.x * self.x + self.y * self.y

    def abs(self):
        return math.sqrt(self.norm())

    def rotate(self, theta):
        return Vector(self.x * math.cos(theta)
                               - self.y * math.sin(theta),
                               self.x * math.sin(theta)
                               + self.y * math.cos(theta))

class Point(Vector):
    def __init__(self, *args, **kargs):
        return super().__init__(*args, **kargs)

class Segment:
    def __init__(self, p1=Point(0, 0), p2=Point(1, 1)):
        self.p1 = p1
        self.p2 = p2

class Line(Segment):
    def __init__(self, *args, **kargs):
        return super().__init__(*args, **kargs)

def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    if a.cross(b) > EPS:
        return 1
    elif a.cross(b) < -EPS:
        return -1
    elif a.dot(b) < -EPS:
        return 2
    elif a.norm() < b.norm():
        return -2
    else:
        return 0

def contains(P, p):
    n = len(P)
    count = 0
    for i in range(n):
        a = P[i]
        b = P[ (i + 1) % n ]
        if a.y > b.y:
            a, b = b, a
        if ccw(p, a, b) == 2:
            return 1
        if ccw(p, a, b) == 1 and b.y > p.y and a.y <= p.y:
            count = count + 1
    if count % 2 == 0:
        return 0
    else:
        return 2

def read_polygon(n):
    P = []
    for _ in range(n):
        line = stdin.readline().strip().split()
        p = Vector(int(line[0]), int(line[1]))
        P.append(p)
    return P

def read_and_print_results(k, P):
    for _ in range(k):
        line = stdin.readline().strip().split()
        p = Vector(int(line[0]), int(line[1]))
        result = contains(P, p)
        print(result)

def __main():
    n = int(input())
    P = read_polygon(n)
    k = int(input())
    read_and_print_results(k, P)

if __name__ == '__main__':
    __main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
readline = stdin.readline


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def eq(a, b):
    return abs(a - b) < 1e-10


def on_line(p, s, e):
    d = dot(p - s, e - s)
    c = cross(p - s, e - s)
    if c == 0 and 0 <= d <= abs(e - s) ** 2:
        return True
    return False


def on_polygon_line(xy, p):
    for i in range(len(p)):
        j = i - 1
        if on_line(xy, p[i], p[j]):
            return True
    return False


def in_polygon(xy, p):
    wn = 0
    for i in range(len(p)):
        j = i - 1
        if 0 == (p[i] - p[j]).imag:
            continue
        vt = (xy - p[j]).imag / (p[i] - p[j]).imag
        tmp = p[i] + vt * (p[i] - p[j])
        if xy.real < tmp.real:
            wn += 1 if p[j].imag < xy.imag <= p[i].imag else\
                 -1 if p[i].imag < xy.imag <= p[j].imag else 0
    return wn

n = int(readline())
p = [map(int, readline().split()) for _ in range(n)]
p = [x + y * 1j for x, y in p]

q = int(readline())
for _ in range(q):
    x, y = map(int, readline().split())
    xy = x + y * 1j
    print(1 if on_polygon_line(xy, p) else 2 if in_polygon(xy, p) else 0)

Submission status: Wrong Answer

Solution code:
n = input()
p = [map(int, raw_input().split()) for i in xrange(n)]
for t in xrange(input()):
    x, y = map(int, raw_input().split())
    cnt = 0
    online = 0
    for i in xrange(n):
        x0 = p[i-1][0] - x
        y0 = p[i-1][1] - y
        x1 = p[i][0] - x
        y1 = p[i][1] - y
        #print "a", x0, y0, x1, y1
        if x0*(y1 - y0) == y0*(x1 - x0):
            online = 1
            break
        if (y0*y1 < 0 or (y0==0 and y1!=0)) and x0 - y0*(x1-x0)/float(y1-y0) > 0:
            #print y0*y1, x0 - float(y0*(x1-x0))/(y1-y0)
            cnt += 1
    if online:
        print 1
    elif cnt % 2:
        print 2
    else:
        print 0

Submission status: Wrong Answer

Solution code:
from math import atan2
n = input()
p = [map(int, raw_input().split()) for i in xrange(n)]
for t in xrange(input()):
    x, y = map(int, raw_input().split())

    inline = 0
    theta = 0.
    for i in xrange(n):
        x0 = p[i-1][0] - x
        y0 = p[i-1][1] - y
        x1 = p[i][0] - x
        y1 = p[i][1] - y

        if x0*y1 == y0*x1:
            inline = 1
            break
        theta += atan2(x0*y1-y0*x1, x0*x1+y0*y1)
    if inline:
        print 1
    elif theta > 1:
        print 2
    else:
        print 0

Submission status: Wrong Answer

Solution code:
def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def string_to_complex(s):
    x, y = map(int, s.split())
    return x + y * 1j

def contains(polygon, point):
    flag = False
    up = False
    down = False
    for v1, v2 in zip(polygon[0:], polygon[1:]):
        a = v1 - point
        b = v2 - point
        if cross(a, b) == 0 and dot(a, b) <= 0:
            return 1
        if a.imag < b.imag:
            if a.imag < 0 and b.imag > 0 and cross(a, b) > 0:
                flag = not flag
            elif a.imag == 0 and up:
                flag = not flag
            up = True
            down = False
        elif a.imag > b.imag:
            if a.imag > 0 and b.imag < 0 and cross(a, b) < 0:
                flag = not flag
            elif a.imag == 0 and down:
                flag = not flag
            up = False
            down = True
    if flag:
        return 2
    else:
        return 0

import sys

file_input = sys.stdin

n = int(file_input.readline())

polygon = [string_to_complex(file_input.readline()) for i in range(n)]
polygon.append(polygon[0])
polygon.append(polygon[1])

q = int(file_input.readline())

for line in file_input:
    t = string_to_complex(line)
    print(contains(polygon, t))

Submission status: Wrong Answer

Solution code:
def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def string_to_complex(s):
    x, y = map(int, s.split())
    return x + y * 1j

def contains(polygon, point):
    flag = False
    up = False
    down = False
    for v1, v2 in zip(polygon[0:], polygon[1:]):
        a = v1 - point
        b = v2 - point
        if cross(a, b) == 0 and dot(a, b) <= 0:
            return 1
        if a.imag < b.imag:
            if a.imag < 0 or (a.imag == 0 and up):
                if b.imag > 0 and cross(a, b) > 0:
                    flag = not flag
            up = True
            down = False
        elif a.imag > b.imag:
            if a.imag > 0 or (a.imag == 0 and down):
                if b.imag < 0 and cross(a, b) < 0:
                    flag = not flag
            up = False
            down = True
    if flag:
        return 2
    else:
        return 0

import sys

file_input = sys.stdin

n = int(file_input.readline())

polygon = [string_to_complex(file_input.readline()) for i in range(n)]
polygon.append(polygon[0])
polygon.append(polygon[1])

q = int(file_input.readline())

for line in file_input:
    t = string_to_complex(line)
    print(contains(polygon, t))

Submission status: Wrong Answer

Solution code:
n = int(input())
g = []
for i in range(n):
    g.append([int(i) for i in input().split()])
q = int(input())

def dot(a, b):
    return sum([i * j for i,j in zip(a, b)])
def sub(a, b):
    return [a[0] - b[0],a[1] - b[1]]
def cross(a, b):
    return  a[0] * b[1] - a[1] * b[0]
def contains(g, p):
    x = False
    for i in range(n):
        a = sub(g[i], p)
        b = sub(g[(i+1)%n], p)
        if abs(cross(a, b)) == 0 and dot(a, b) < 0: 
            return 1
        if a[1] > b[1]:
            a,b=b,a
        if a[1] < 0 and 0 < b[1] and abs(cross(a,b)) > 0:
            x = not x
    return 2 if x else 0
for i in range(q):
    x,y = map(int, input().split())
    print(contains(g, [x,y]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import collections
import math


class Vector2(collections.namedtuple("Vector2", ["x",  "y"])):

    def __add__(self, other):
        return Vector2(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vector2(self.x - other.x, self.y - other.y)

    def __mul__(self, scalar):
        return Vector2(self.x * scalar, self.y * scalar)

    def __neg__(self):
        return Vector2(-self.x, -self.y)

    def __pos__(self):
        return Vector2(+self.x, +self.y)

    def __abs__(self):  # norm
        return math.sqrt(float(self.x * self.x + self.y * self.y))

    def __truediv__(self, scalar):
        return Vector2(self.x / scalar, self.y / scalar)

    def abs2(self):
        return float(self.x * self.x + self.y * self.y)

    def dot(self, other):  # dot product
        return self.x * other.x + self.y * other.y

    def cross(self, other):  # cross product
        return self.x * other.y - self.y * other.x


def getDistanceSP(segment, point):
    p = point
    p1, p2 = segment
    if (p2 - p1).dot(p - p1) < 0:
        return abs(p - p1)
    if (p1 - p2).dot(p - p2) < 0:
        return abs(p - p2)
    return abs((p2 - p1).cross(p - p1)) / abs(p2 - p1)


def getDistance(s1, s2):
    a, b = s1
    c, d = s2
    if intersect(s1, s2):  # intersect
        return 0
    return min(getDistanceSP(s1, c), getDistanceSP(s1, d), getDistanceSP(s2, a), getDistanceSP(s2, b))


def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    if a.cross(b) > 0:
        return 1  # COUNTER_CLOCKWISE
    elif a.cross(b) < 0:
        return -1  # CLOCKWISE
    elif a.dot(b) < 0:
        return 2  # ONLINE_BACK
    elif abs(a) < abs(b):
        return -2  # ONLINE_FRONT
    else:
        return 0  # ON_SEGMENT


def intersect(s1, s2):
    a, b = s1
    c, d = s2
    return ccw(a, b, c) * ccw(a, b, d) <= 0 and ccw(c, d, a) * ccw(c, d, b) <= 0


def project(l, p):
    p1, p2 = l
    base = p2 - p1
    hypo = p - p1
    return p1 + base * (hypo.dot(base) / abs(base)**2)


class Circle():
    def __init__(self, c, r):
        self.c = c
        self.r = r


def getCrossPoints(c, l):
    pr = project(l, c.c)
    p1, p2 = l
    e = (p2 - p1) / abs(p2 - p1)
    base = math.sqrt(c.r * c.r - (pr - c.c).abs2())
    return [pr + e * base, pr - e * base]


def polar(r, a):
    return Vector2(r * math.cos(a), r * math.sin(a))


def getCrossPointsCircle(c1, c2):
    base = c2.c - c1.c
    d = abs(base)
    a = math.acos((c1.r**2 + d**2 - c2.r**2) / (2 * c1.r * d))
    t = math.atan2(base.y, base.x)
    return [c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a)]


def contains(g, p):
    n = len(g)
    x = 0
    for i in range(n):
        a = g[i] - p
        b = g[(i + 1) % n] - p
        if a.cross(b) == 0 and a.dot(b) < 0:
            return 1
        if a.y > b.y:
            a, b = b, a
        if a.y <= 0 and b.y > 0 and a.cross(b) > 0:
            x += 1

    if x % 2 == 1:
        return 2
    else:
        return 0


if __name__ == '__main__':

    n = int(input())
    g = []
    for _ in range(n):
        a, b = map(int, input().split())
        g.append(Vector2(a, b))
    q = int(input())
    for _ in range(q):
        c, d = map(int, input().split())
        print(contains(g, Vector2(c, d)))

Submission status: Wrong Answer

Solution code:
import math

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Vector():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def inner_product(self, vec):
        return self.x*vec.x + self.y*vec.y

    def outer_product(self, vec):
        return self.x*vec.y - self.y*vec.x

    def norm(self):
        return math.sqrt(self.x**2 + self.y**2)

    def polar(self):
        r = self.norm()
        theta = math.atan2(self.y, self.x)
        return r, theta


class Segment():
    def __init__(self, p1=None, p2=None):
        self.p1 = p1
        self.p2 = p2

    def is_intersect(self, seg):
        a = (seg.p1.x - seg.p2.x) * (self.p1.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p1.x)
        b = (seg.p1.x - seg.p2.x) * (self.p2.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p2.x)
        c = (self.p1.x - self.p2.x) * (seg.p1.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p1.x)
        d = (self.p1.x - self.p2.x) * (seg.p2.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p2.x)
        e = (self.p1.x - seg.p1.x)*(self.p2.x - seg.p2.x)
        f = (self.p1.x - seg.p2.x)*(self.p2.x - seg.p1.x)
        g = (self.p1.y - seg.p1.y)*(self.p2.y - seg.p2.y)
        h = (self.p1.y - seg.p2.y)*(self.p2.y - seg.p1.y)
        return a*b <= 0 and c*d <= 0 and (e <= 0 or f <= 0) and (g <= 0 or h <= 0)

    def on_segment(self, pnt):
        if self.p1 == pnt or self.p2 == pnt: return True
        a, b = Vector(self.p2.x - self.p1.x, self.p2.y - self.p1.y), Vector(pnt.x - self.p1.x, pnt.y - self.p1.y)
        a_r, a_theta = a.polar()
        b_r, b_theta = b.polar()
        if a_theta == b_theta:
            if 0 < b_r/a_r and b_r/a_r < 1:
                return True
        return False

n = int(input())
points = []
for i in range(n):
    x, y = list(map(int, input().split(' ')))
    points.append(Point(x, y))
points.append(points[0])
segments = [Segment(points[i], points[i+1]) for i in range(n)]

q = int(input())
for i in range(q):
    x, y = list(map(int, input().split(' ')))
    right, left = Segment(Point(x, y), Point(10001, y)), Segment(Point(x, y), Point(-10001, y))
    up, down = Segment(Point(x, y), Point(x, 10001)), Segment(Point(x, y), Point(x, -10001))
    r_int, l_int, u_int, d_int = 0, 0, 0, 0
    on_segment = False
    for seg in segments:
        if seg.on_segment(Point(x, y)):
            on_segment = True
            break
        if seg.is_intersect(right): r_int += 1
        if seg.is_intersect(left): l_int += 1
        if seg.is_intersect(up): u_int += 1
        if seg.is_intersect(down): d_int += 1

    if on_segment:
        print(1)
    elif r_int%2 == 1 or l_int%2 == 1 or u_int%2 == 1 or d_int%2 == 1:
        print(2)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import math

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __eq__(self, pnt):
        if self.x == pnt.x and self.y == pnt.y: return True
        return False

class Vector():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def inner_product(self, vec):
        return self.x*vec.x + self.y*vec.y

    def outer_product(self, vec):
        return self.x*vec.y - self.y*vec.x

    def norm(self):
        return math.sqrt(self.x**2 + self.y**2)

    def polar(self):
        r = self.norm()
        theta = math.atan2(self.y, self.x)
        return r, theta


class Segment():
    def __init__(self, p1=None, p2=None):
        self.p1 = p1
        self.p2 = p2

    def is_intersect(self, seg):
        a = (seg.p1.x - seg.p2.x) * (self.p1.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p1.x)
        b = (seg.p1.x - seg.p2.x) * (self.p2.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p2.x)
        c = (self.p1.x - self.p2.x) * (seg.p1.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p1.x)
        d = (self.p1.x - self.p2.x) * (seg.p2.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p2.x)
        e = (self.p1.x - seg.p1.x)*(self.p2.x - seg.p2.x)
        f = (self.p1.x - seg.p2.x)*(self.p2.x - seg.p1.x)
        g = (self.p1.y - seg.p1.y)*(self.p2.y - seg.p2.y)
        h = (self.p1.y - seg.p2.y)*(self.p2.y - seg.p1.y)
        return a*b <= 0 and c*d <= 0 and (e <= 0 or f <= 0) and (g <= 0 or h <= 0)

    def on_segment(self, pnt):
        if self.p1 == pnt or self.p2 == pnt: return True
        a, b = Vector(self.p2.x - self.p1.x, self.p2.y - self.p1.y), Vector(pnt.x - self.p1.x, pnt.y - self.p1.y)
        a_r, a_theta = a.polar()
        b_r, b_theta = b.polar()
        if a_theta == b_theta:
            if 0 < b_r/a_r and b_r/a_r < 1:
                return True
        return False

n = int(input())
points = []
for i in range(n):
    x, y = list(map(int, input().split(' ')))
    points.append(Point(x, y))
points.append(points[0])
segments = [Segment(points[i], points[i+1]) for i in range(n)]

q = int(input())
for i in range(q):
    x, y = list(map(int, input().split(' ')))
    right, left = Segment(Point(x, y), Point(10001, y)), Segment(Point(x, y), Point(-10001, y))
    up, down = Segment(Point(x, y), Point(x, 10001)), Segment(Point(x, y), Point(x, -10001))
    r_int, l_int, u_int, d_int = 0, 0, 0, 0
    on_segment = False
    for seg in segments:
        if seg.on_segment(Point(x, y)):
            on_segment = True
            break
        if seg.is_intersect(right): r_int += 1
        if seg.is_intersect(left): l_int += 1
        if seg.is_intersect(up): u_int += 1
        if seg.is_intersect(down): d_int += 1

    if on_segment:
        print(1)
    elif r_int%2 == 1 or l_int%2 == 1 or u_int%2 == 1 or d_int%2 == 1:
        print(2)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import math

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, pnt):
        if self.x == pnt.x and self.y == pnt.y: return True
        return False

class Vector():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def inner_product(self, vec):
        return self.x*vec.x + self.y*vec.y

    def outer_product(self, vec):
        return self.x*vec.y - self.y*vec.x

    def norm(self):
        return math.sqrt(self.x**2 + self.y**2)

    def polar(self):
        r = self.norm()
        theta = math.atan2(self.y, self.x)
        return r, theta


class Segment():
    def __init__(self, p1=None, p2=None):
        self.p1 = p1
        self.p2 = p2

    def is_intersect(self, seg):
        a = (seg.p1.x - seg.p2.x) * (self.p1.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p1.x)
        b = (seg.p1.x - seg.p2.x) * (self.p2.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p2.x)
        c = (self.p1.x - self.p2.x) * (seg.p1.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p1.x)
        d = (self.p1.x - self.p2.x) * (seg.p2.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p2.x)
        e = (self.p1.x - seg.p1.x)*(self.p2.x - seg.p2.x)
        f = (self.p1.x - seg.p2.x)*(self.p2.x - seg.p1.x)
        g = (self.p1.y - seg.p1.y)*(self.p2.y - seg.p2.y)
        h = (self.p1.y - seg.p2.y)*(self.p2.y - seg.p1.y)
        return a*b <= 0 and c*d <= 0 and (e <= 0 or f <= 0) and (g <= 0 or h <= 0)

    def on_segment(self, pnt):
        if self.p1 == pnt or self.p2 == pnt:
            return True
        a, b = Vector(self.p2.x - self.p1.x, self.p2.y - self.p1.y), Vector(pnt.x - self.p1.x, pnt.y - self.p1.y)
        a_r, a_theta = a.polar()
        b_r, b_theta = b.polar()
        if a_theta == b_theta:
            if 0 < b_r/a_r and b_r/a_r < 1:
                return True
        return False

n = int(input())
points = []
for i in range(n):
    x, y = list(map(int, input().split(' ')))
    points.append(Point(x, y))
points.append(points[0])
segments = [Segment(points[i], points[i+1]) for i in range(n)]

q = int(input())
for i in range(q):
    x, y = list(map(int, input().split(' ')))
    right, left = Segment(Point(x, y), Point(10001, y)), Segment(Point(x, y), Point(-10001, y))
    up, down = Segment(Point(x, y), Point(x, 10001)), Segment(Point(x, y), Point(x, -10001))
    r_int, l_int, u_int, d_int = 0, 0, 0, 0
    on_segment = False
    for seg in segments:
        if seg.on_segment(Point(x, y)):
            on_segment = True
            break
        if seg.is_intersect(right): r_int += 1
        if seg.is_intersect(left): l_int += 1
        if seg.is_intersect(up): u_int += 1
        if seg.is_intersect(down): d_int += 1

    if on_segment:
        print(1)
    elif (r_int%2 == 1 or l_int%2 == 1) and (u_int%2 == 1 or d_int%2 == 1):
        print(2)
    else:
        print(0)