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: Accepted

Solution code:
import math

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)
    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)
    def __mul__(self, other):
        return Point(self.x * other, self.y * other)
    def __truediv__(self, other):
        return Point(self.x / other, self.y / other)
    def __repr__(self):
        return str(round(self.x, 8)) + ' ' + str(round(self.y, 8))
    def __lt__(self, other):
        if self.x == other.x:
            return self.y < other.y
        else:
            return self.x < other.x

class Vector(Point):
    pass

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

class Segment(Line):
    pass

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

class Polygon:
    def __init__(self, points):
        self.points = points

def points_to_vector(p1, p2):
    x = p1.x - p2.x
    y = p1.y - p2.y
    return Vector(x, y)

def vector(p):
    return Vector(p.x, p.y)

def dot(v1, v2):
    return v1.x * v2.x + v1.y * v2.y

def cross(v1, v2):
    return v1.x * v2.y - v1.y * v2.x

def norm(v):
    return v.x**2 + v.y**2

def distance(v):
    return math.sqrt(norm(v))

def project(s, p):
    base = points_to_vector(s.p1, s.p2)
    hypo = points_to_vector(p, s.p1)
    r = dot(hypo, base) / norm(base)
    return s.p1 + base * r

def reflect(s, p):
    return p + (project(s, p) -p) * 2

def get_distance(s1, s2):
    if intersect_s(s1, s2):
        return 0
    d1 = get_distance_sp(s1, s2.p1)
    d2 = get_distance_sp(s1, s2.p2)
    d3 = get_distance_sp(s2, s1.p1)
    d4 = get_distance_sp(s2, s1.p2)
    return min(d1, min(d2, min(d3, d4)))

def get_distance_pp(p1, p2):
    return distance(p1 - p2)

def get_distance_lp(l, p):
    return abs(cross(l.p2 - l.p1, p - l.p1) / distance(l.p2 - l.p1))

def get_distance_sp(s, p):
    if dot(s.p2 - s.p1, p - s.p1) < 0:
        return distance(p - s.p1)
    elif dot(s.p1 - s.p2, p - s.p2) < 0:
        return distance(p - s.p2)
    else:
        return get_distance_lp(s, p)

def ccw(p0, p1, p2):
    EPS = 1e-10
    COUNTER_CLOCKWISE = 1
    CLOCKWISE = -1
    ONLINE_BACK = 2
    ONLINE_FRONT = -2
    ON_SEGMENT = 0
    v1 = p1 - p0
    v2 = p2 - p0
    if cross(v1, v2) > EPS:
        return COUNTER_CLOCKWISE
    elif cross(v1, v2) < -EPS:
        return CLOCKWISE
    elif dot(v1, v2) < -EPS:
        return ONLINE_BACK
    elif norm(v1) < norm(v2):
        return ONLINE_FRONT
    else:
        return ON_SEGMENT

def intersect_p(p1, p2, p3, p4):
    return ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 and ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0

def intersect_s(s1, s2):
    return intersect_p(s1.p1, s1.p2, s2.p1, s2.p2)

def get_cross_point(s1, s2):
    base = s2.p2 - s2.p1
    d1 = abs(cross(base, s1.p1 - s2.p1))
    d2 = abs(cross(base, s1.p2 - s2.p1))
    t = d1 / (d1 + d2)
    return s1.p1 + (s1.p2 - s1.p1) * t

def get_cross_points(c, l):
    pr = project(l, c.c)
    e = (l.p2 - l.p1) / distance(l.p2 - l.p1)
    base = math.sqrt(c.r**2 - norm(pr - c.c))
    return pr + e * base, pr - e * base

def arg(p):
    return math.atan2(p.y, p.x)

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

def get_cross_points_cirlces(c1, c2):
    d = distance(c1.c - c2.c)
    a = math.acos((c1.r**2 + d * d - c2.r**2) / (2 * c1.r * d))
    t = arg(c2.c - c1.c)
    return c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a)

def pol_contains(g, p):
    EPS = 1e-10
    n = len(g.points)
    x = False
    for i in range(n):
        a = g.points[i] - p
        b = g.points[(i+1)%n] - p
        if abs(cross(a, b)) < EPS and dot(a, b) < EPS:
            return 1
        if a.y > b.y:
            a, b = b, a
        if a.y < EPS < b.y and cross(a, b) > EPS:
            x = not x
    if x % 2 == 0:
        return 0
    else:
        return 2

import sys
# sys.stdin = open('input.txt')

n = int(input())
points = []
for i in range(n):
    x, y = map(int, input().split())
    points.append(Point(x, y))
g = Polygon(points)
q = int(input())
for i in range(q):
    x, y = map(int, input().split())
    p = Point(x, y)
    print(pol_contains(g, p))

Submission status: Accepted

Solution code:
def inside_polygon(p0, qs):
    cnt = 0
    L = len(qs)
    x, y = p0
    for i in range(L):
        x0, y0 = qs[i-1]; x1, y1 = qs[i]
        x0 -= x; y0 -= y
        x1 -= x; y1 -= y

        cv = x0*x1 + y0*y1
        sv = x0*y1 - x1*y0
        if sv == 0 and cv <= 0:
            return 1

        if not y0 < y1:
            x0, x1 = x1, x0
            y0, y1 = y1, y0

        if y0 <= 0 < y1 and x0*(y1 - y0) > y0*(x1 - x0):
            cnt += 1
    return 2 if cnt % 2 == 1 else 0

def solve():
    N = int(input())
    qs = [list(map(int, input().split())) for i in range(N)]

    Q = int(input())
    for i in range(Q):
        *p0, = map(int, input().split())
        print(inside_polygon(p0, qs))
solve()

Submission status: Accepted

Solution code:
from functools import singledispatch
import math

EPS = 1e-10

COUNTER_CLOCKWISE = 1
CLOCKWISE = -1
ONLINE_BACK = 2
ONLINE_FRONT = -2
ON_SEGMENT = 0

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

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

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

    def __add__(self, point):
        # + 演算子での挙動を指定
        return Point(self.x+point.x, self.y+point.y)

    def __sub__(self, point):
        # - 演算子での挙動を指定
        return Point(self.x-point.x, self.y-point.y)

    def __mul__(self, a):
        # * 演算子での挙動を指定
        return Point(a*self.x, a*self.y)

    def __truediv__(self, a):
        # / 演算子での挙動を指定
        return Point(self.x/a, self.y/a)

    def __abs__(self):
        # abs関数での挙動を指定
        return math.sqrt(self.norm())

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

    def __eq__(self, point):
        # == 演算子での挙動を指定
        return abs(self.x-point.x) < EPS and abs(self.y-point.y) <EPS

def dot(a, b):
    return a.x*b.x+a.y*b.y

def cross(a, b):
    return a.x*b.y - a.y*b.x

def isOrthogonal(a, b):
    return dot(a, b) == 0

def isParallel(a, b):
    return cross(a, b) == 0

def project(s, p):
    #s: Segment(), p: Point()
    base = s.p2 - s.p1
    r = dot(p-s.p1, base)/base.norm()
    return s.p1+base*r

def reflect(s, p):
    return p+(project(s, p)-p)*2

@singledispatch
def get_distance(a, b):
    return abs(a-b)

def get_distance_lp(l, p):
    return abs(cross(l.p2-l.p1, p-l.p1)/abs(l.p2-l.p1))

def get_distance_sp(s, p):
    if dot(s.p2-s.p1, p-s.p1) < 0:
        return abs(p-s.p1)
    if dot(s.p1-s.p2, p-s.p2) < 0:
        return abs(p-s.p2)
    return get_distance_lp(s, p)
    
@get_distance.register(Segment)
def _(s1, s2):
    if intersect(s1, s2):
        return 0
    return min([get_distance_sp(s1, s2.p1), get_distance_sp(s1, s2.p2),
                get_distance_sp(s2, s1.p1), get_distance_sp(s2, s1.p2)])

def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    if cross(a, b) > EPS:
        return COUNTER_CLOCKWISE
    if cross(a, b) < -EPS:
        return CLOCKWISE
    if dot(a, b) < -EPS:
        return ONLINE_BACK
    if a.norm() < b.norm():
        return ONLINE_FRONT
    return ON_SEGMENT

@singledispatch
def intersect(p1, p2, p3, p4):
    return (ccw(p1, p2, p3)*ccw(p1, p2, p4) <= 0
            and ccw(p3, p4, p1)*ccw(p3, p4, p2) <= 0)

@intersect.register(Segment)
def _(s1, s2):
    return intersect(s1.p1, s1.p2, s2.p1, s2.p2)

def get_cross_point(s1, s2):
    base = s2.p2 - s2.p1
    d1 = abs(cross(base, s1.p1-s2.p1))
    d2 = abs(cross(base, s1.p2-s2.p1))
    t = d1/(d1+d2)
    return s1.p1 + (s1.p2-s1.p1)*t

def get_cross_points(c, l):
    # 次の行のコメントのコードは、新しいintersect関数を作る必要があり(おそらくpython3.7以上必須)、手間取るので割愛します。
    # assert(intersect(c, l))
    pr = project(l, c.c)
    e = (l.p2 - l.p1)/abs(l.p2-l.p1)
    base = (c.r**2-(pr-c.c).norm())**0.5
    return (pr+e*base, pr-e*base)

def arg(p):
    return math.atan2(p.y, p.x)

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

def get_cross_points_(c1, c2):
    # 関数名かぶるので、_つけました。
    # python3.7以上でsingledispatchを使えば同じ関数名も可能ですが、
    # atcoderのpython3.4も想定しているため、関数名を変えておきます。
    # assert(intersect(c, c))
    d = abs(c1.c-c2.c)
    a = math.acos((c1.r**2+d**2-c2.r**2)/(2*c1.r*d))
    t = arg(c2.c-c1.c)
    return (c1.c+polar(c1.r, t+a), c1.c+polar(c1.r, t-a))

def contains(g, p):
    # gは多角形の頂点を順番に並べたリスト/タプル
    n = len(g)
    x = False
    for i in range(n):
        a = g[i]-p
        b = g[(i+1)%n]-p
        if abs(cross(a, b)) < EPS and dot(a, b) < EPS:
            return 1
        if a.y > b.y:
            a, b = b, a
        if a.y < EPS and EPS < b.y and cross(a, b) > EPS:
            x = not x
    return 2 if x else 0

if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    n = int(input())
    g = [0]*n   # 初期化
    for i in range(n):
        x, y = map(int, input().split())
        p = Point(x, y)
        g[i] = p
    q = int(input())
    for _ in range(q):
        x, y = map(int, input().split())
        p = Point(x, y)
        print(contains(g, p))

Submission status: Accepted

Solution code:
from math import pi, cos, sin, atan2
from operator import itemgetter
EPS = 10**(-9)

def eq(value1, value2):
    return abs(value1-value2) <= EPS

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __str__(self):
        #return "{0:.8f} {1:.8f}".format(self.x, self.y)
        return "{0} {1}".format(self.x, self.y)
    
    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)
    
    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)
    
    def __mul__(self, scal):
        return Point(self.x*scal, self.y*scal)
    
    def __truediv__(self, scal):
        return Point(self.x/scal, self.y/scal)
    
    def __eq__(self, other):
        return eq(self.x, other.x) and eq(self.y, other.y)

    # 原点からの距離
    def __abs__(self):
        return (self.x**2+self.y**2)**0.5

    def arg(self):
        return atan2(self.y, self.x)
    
# 原点を中心にrad角だけ回転した点
def Rotation(vec: Point, rad):
    return Point(vec.x*cos(rad)-vec.y*sin(rad), vec.x*sin(rad)+vec.y*cos(rad))


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


class Line():
    # 点a, bを通る
    def __init__(self, a, b):
        self.a = a
        self.b = b
    
    def __str__(self):
        return "[({0}, {1}) - ({2}, {3})]".format(self.a.x, self.a.y, self.b.x, self.b.y)
    
    def arg(self):
        return (a-b).arg() % pi

    # pointを通って平行
    def par(self, point):
        return Line(point, point+(self.a-self.b))

    # pointを通って垂直
    def tan(self, point):
        return Line(point, point + Rotation(self.a-self.b, pi/2))


class Segment(Line):
    def __init__(self, a, b):
        super().__init__(a, b)


# 符号付き面積
def cross(vec1: Point, vec2: Point):
    return vec1.x*vec2.y - vec1.y*vec2.x

# 内積
def dot(vec1: Point, vec2: Point):
    return vec1.x*vec2.x + vec1.y*vec2.y

# 点a->b->cの回転方向
def ccw(a, b, c):
    if cross(b-a, c-a) > EPS: return +1 # COUNTER_CLOCKWISE
    if cross(b-a, c-a) < -EPS: return -1 # CLOCKWISE
    if dot(c-a, b-a) < -EPS: return +2 # c -> a -> b
    if abs(b-a) < abs(c-a): return -2 # a -> b -> c
    return 0 # a -> c -> b


# pのlへの射影
def projection(l, p):
    t = dot(l.b-l.a, p-l.a) / abs(l.a-l.b)**2
    return l.a + (l.b-l.a)*t

# pのlによる反射
def reflection(l, p):
    return p + (projection(l, p) - p)*2

def isPararell(l1, l2):
    return eq(cross(l1.a-l1.b, l2.a-l2.b), 0)

def isVertical(l1, l2):
    return eq(dot(l1.a-l1.b, l2.a-l2.b), 0)


def Intersect_lp(l, p):
    return abs(ccw(l.a, l.b, p)) != 1

def Intersect_ll(l1, l2):
    return not isPararell(l1, l2) or Intersect_lp(l1, l2.a)

def Intersect_sp(s, p):
    return ccw(s.a, s.b, p) == 0

def Intersect_ss(s1, s2):
    return ccw(s1.a, s1.b, s2.a)*ccw(s1.a, s1.b, s2.b) <= 0 and ccw(s2.a, s2.b, s1.a)*ccw(s2.a, s2.b, s1.b) <= 0

def Intersect_ls(l, s):
    return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < EPS

def Intersect_cp(c, p):
    return abs(abs(c.p - p) - c.r) < EPS

def Intersect_cl(c, l):
    return distance_lp(l, c.p) <= c.r + EPS

def Intersect_cs(c, s):
    h = projection(s, c.p)
    if abs(h - c.p)**2 - c.r**2 > EPS: return 0 # 遠い
    d1 = abs(c.p - s.a); d2 = abs(c.p - s.b)
    if d1 < c.r - EPS and d2 < c.r - EPS: return 0 # どちらも内側
    if (d1 < c.r - EPS and d2 > c.r + EPS) or (d1 > c.r + EPS and d2 < c.r - EPS): return 1 # 片方だけ内側
    if dot(s.a-h, s.b-h) < 0: return 2 # 2点で交わる
    return 0


def Intersect_cc(c1, c2):
    if c1.r < c2.r:
        c1, c2 = c2, c1
    d = abs(c1.p - c2.p)
    if eq(c1.r + c2.r, d): return 3 # 内接
    if eq(c1.r - c2.r, d): return 1 # 外接
    if c1.r + c2.r < d: return 4 # 含まれてる
    if c1.r - c2.r < d: return 2 # 2交点持つ
    return 0 # 離れてる


def distance_pp(p1, p2):
    return abs(p1-p2)

def distance_lp(l, p):
    return abs(projection(l,p)-p)

def distance_ll(l1, l2):
    return 0 if Intersect_ll(l1, l2) else distance_lp(l1, l2.a)

def distance_sp(s, p):
    r = projection(s, p)
    if Intersect_sp(s, r): return abs(r-p)
    return min(abs(s.a-p), abs(s.b-p))

def distance_ss(s1, s2):
    if Intersect_ss(s1, s2): return 0
    return min([distance_sp(s1, s2.a), distance_sp(s1, s2.b), distance_sp(s2, s1.a), distance_sp(s2, s1.b)])

def distance_ls(l, s):
    if Intersect_ls(l, s): return 0
    return min(distance_lp(l, s.a), distance_lp(l, s.b))


def crosspoint_ll(l1, l2):
    A = cross(l1.b - l1.a, l2.b - l2.a)
    B = cross(l1.b - l1.a, l1.b - l2.a)
    if eq(abs(A), 0) and eq(abs(B), 0): return l2.a
    return l2.a + (l2.b - l2.a) * B / A

def crosspoint_ss(s1, s2):
    return crosspoint_ll(s1, s2)

def crosspoint_lc(l, c):
    p = projection(l, c.p)
    if eq(distance_lp(l, c.p), c.r): return [p]
    e = (l.b - l.a) / abs(l.b-l.a)
    dis = (c.r**2-abs(p-c.p)**2)**0.5
    return [p + e*dis, p - e*dis]

def crosspoint_sc(s, c):
    l = Line(s.a, s.b)
    if Intersect_cs(c, s) == 2: return crosspoint_lc(l, c)
    Points = crosspoint_lc(l, c)
    if len(Points) == 1:
        return Points
    if dot(s.a-Points[0], s.b-Points[0]) < 0: return [Points[0]]
    return [Points[1]]


def crosspoint_cc(c1, c2):
    d = abs(c1.p-c2.p)
    if not abs(c1.r-c2.r) <= d <= c1.r+c2.r:
        return []
    mid_p = (c2.p * (c1.r**2-c2.r**2+d**2) + c1.p * (c2.r**2-c1.r**2+d**2)) / (2*d**2)
    tanvec = Rotation(c1.p-c2.p, pi/2)
    return crosspoint_lc(Line(mid_p, mid_p+tanvec), c1)


# pからのcの接点
def tangent_cp(c, p):
    return crosspoint_cc(c, Circle(p, (abs(p-c.p)**2 - c.r**2)**0.5))

# 共通接線
def tangent_cc(c1, c2):
    pass


def isConvex(Points):
    n = len(Points)
    for i in range(n):
        if ccw(Points[i-1], Points[i], Points[(i+1)%n]) == -1: return False
    return True


def ConvexHull(Points):
    Points.sort(key=lambda p: p.y)
    Points.sort(key=lambda p: p.x)

    Qs = []
    for p in Points:
        while len(Qs) > 1 and ccw(Qs[-2], Qs[-1], p) == -1:
            Qs.pop()
        Qs.append(p)
        
    t = len(Qs)
    Qs.pop()
    for p in reversed(Points):
        while len(Qs) > t and ccw(Qs[-2], Qs[-1], p) == -1:
            Qs.pop()
        Qs.append(p)
    Qs.pop()

    return Qs

def contains(Points, p):
    inside = False
    for i in range(len(Points)):
        a = Points[i-1] - p
        b = Points[i] - p
        if a.y > b.y: a, b = b, a
        if a.y <= 0 and 0 < b.y and cross(a, b) < 0:
            inside = not inside
        if cross(a, b) == 0 and dot(a, b) <= 0:
            return 1 #辺上
    return 2 if inside else 0
    

def area(Points):
    S = 0
    for i in range(len(Points)):
        S += cross(Points[i-1], Points[i])/2
    return S



import sys
input = sys.stdin.readline

def verify_1A():
    p1x, p1y, p2x, p2y = map(int, input().split())
    l = Line(Point(p1x, p1y), Point(p2x, p2y))
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for px, py in Query:
        p = Point(px, py)
        print(projection(l, p))

def verify_1B():
    p1x, p1y, p2x, p2y = map(int, input().split())
    l = Line(Point(p1x, p1y), Point(p2x, p2y))
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for px, py in Query:
        p = Point(px, py)
        print(reflection(l, p))

def verify_1C():
    p1x, p1y, p2x, p2y = map(int, input().split())
    p1 = Point(p1x, p1y); p2 = Point(p2x, p2y)
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for px, py in Query:
        p = Point(px, py)
        result = ccw(p1, p2, p)
        if result == 1:
            print("COUNTER_CLOCKWISE")
        elif result == -1:
            print("CLOCKWISE")
        elif result == 2:
            print("ONLINE_BACK")
        elif result == -2:
            print("ONLINE_FRONT")
        else:
            print("ON_SEGMENT")

def verify_2A():
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y in Query:
        l1 = Line(Point(p0x, p0y), Point(p1x, p1y))
        l2 = Line(Point(p2x, p2y), Point(p3x, p3y))
        if isPararell(l1, l2):
            print(2)
        elif isVertical(l1, l2):
            print(1)
        else:
            print(0)

def verify_2B():
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y in Query:
        s1 = Segment(Point(p0x, p0y), Point(p1x, p1y))
        s2 = Segment(Point(p2x, p2y), Point(p3x, p3y))
        if Intersect_ss(s1, s2):
            print(1)
        else:
            print(0)


def verify_2C():
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y in Query:
        s1 = Segment(Point(p0x, p0y), Point(p1x, p1y))
        s2 = Segment(Point(p2x, p2y), Point(p3x, p3y))
        print(crosspoint_ss(s1, s2))  

def verify_2D():
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y in Query:
        s1 = Segment(Point(p0x, p0y), Point(p1x, p1y))
        s2 = Segment(Point(p2x, p2y), Point(p3x, p3y))
        print("{:.8f}".format(distance_ss(s1, s2)))

def verify_3A():
    Q = int(input())
    Points = [Point(*map(int, input().split())) for _ in range(Q)]
    S = area(Points)
    print("{:.1f}".format(S))

def verify_3B():
    Q = int(input())
    Points = [Point(*map(int, input().split())) for _ in range(Q)]
    print(1 if isConvex(Points) else 0)

def verify_3C():
    N = int(input())
    Points = [Point(*map(int, input().split())) for _ in range(N)]
    Q = int(input())
    Query = [Point(*map(int, input().split())) for _ in range(Q)]
    for p in Query:
        print(contains(Points, p))

verify_3C()

def verify_4A():
    Q = int(input())
    Points = [Point(*map(int, input().split())) for _ in range(Q)]
    Qs = ConvexHull(Points)
    min_y = 10**10
    min_x = 10**10
    for i, p in enumerate(Qs):
        if p.y < min_y:
            min_y = p.y
            min_x = p.x
            min_ind = i
        elif p.y == min_y and p.x < min_x:
            min_x = p.x
            min_ind = i
    Qs = Qs[min_ind:] + Qs[:min_ind]
    print(len(Qs))
    print("\n".join([str(p.x) + " " + str(p.y) for p in Qs]))

def verify_7A():
    c1x, c1y, c1r = map(int, input().split())
    c2x, c2y, c2r = map(int, input().split())
    print(Intersect_cc(Circle(Point(c1x, c1y), c1r), Circle(Point(c2x, c2y), c2r)))

def verify_7D():
    cx, cy, cr = map(int, input().split())
    c = Circle(Point(cx, cy), cr)
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for x1, y1, x2, y2 in Query:
        Points = crosspoint_lc(Line(Point(x1, y1), Point(x2,y2)), c)
        if len(Points) == 1:
            Points.append(Points[-1])
        Points.sort(key=lambda p: p.y)
        Points.sort(key=lambda p: p.x)
        print(*Points)

def verify_7E():
    c1x, c1y, c1r = map(int, input().split())
    c1 = Circle(Point(c1x, c1y), c1r)
    c2x, c2y, c2r = map(int, input().split())
    c2 = Circle(Point(c2x, c2y), c2r)

    Points = crosspoint_cc(c1, c2)
    if len(Points) == 1:
        Points.append(Points[-1])
    Points.sort(key=lambda p: p.y)
    Points.sort(key=lambda p: p.x)
    print(*Points)  

def verify_7F():
    px, py = map(int, input().split())
    cx, cy, cr = map(int, input().split())
    Points = tangent_cp(Circle(Point(cx, cy), cr), Point(px, py))
    if len(Points) == 1:
        Points.append(Points[-1])
    Points.sort(key=lambda p: p.y)
    Points.sort(key=lambda p: p.x)
    print(*Points, sep="\n")

Submission status: Accepted

Solution code:
import sys
if sys.version_info[0]>=3: raw_input=input

cross=lambda a,b: (a.conjugate()*b).imag
dot=lambda a,b: (a.conjugate()*b).real

def solve(poly, p):
	f=False
	for i in range(len(poly)):
		a=poly[i]-p
		b=poly[(i+1)%len(poly)]-p
		if a.imag>b.imag: a,b=b,a
		if a.imag<=0 and 0<b.imag and cross(a,b)<0: f=not f
		if cross(a,b)==0 and dot(a,b)<=0: return 1
	return 2 if f else 0

checkio=lambda data: solve([complex(*e) for e in data[0]],complex(*data[1]))

n=int(raw_input())
poly=[[float(e) for e in raw_input().split()] for i in range(n)]
n=int(raw_input())
try:
	for i in range(n):
		print(checkio([poly,[float(e) for e in raw_input().split()]]))
except EOFError:
	pass

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

# coding: utf-8
# Your code here!
import math

EPS = 0.0000000001

COUNTER_CLOCKWISE = 1
CLOCKWISE = -1
ONLINE_BACK = 2
ONLINE_FRONT = -2
ON_SEGMENT = 0

IN = 2
ON = 1
OUT = 0

class Point:
    
    global EPS
    
    def __init__(self, x = 0, y = 0):
        self.x = x
        self.y = y
        
        
    def __add__(a, b):
        s = a.x + b.x
        t = a.y + b.y
        return Point(s, t)
        
    def __sub__(a, b):
        s = a.x - b.x
        t = a.y - b.y
        return Point(s, t)
            
    def __mul__(self, a):
        s = a * self.x
        t = a * self.y
        return Point(s, t)
        
    def __truediv__(self, a):
        s = self.x / a
        t = self.y / a
        return Point(s, t)
            
            
            
            
    def norm(self):
        return self.x * self.x + self.y * self.y
        
    def abs(self):
        return self.norm() ** 0.5
            
    
            
            
    def __eq__(self, other):
        return abs(self.x - other.y) < self.EPS and abs(self.y - other.y) < self.EPS
            
            
            
    def dot(self, b):
        return self.x * b.x + self.y * b.y
        
    def cross(self, b):
        return self.x * b.y - self.y * b.x
    
    
class Segment:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2

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

def project(s, p):
    base = s.p2 - s.p1
    hypo = p - s.p1
    r = hypo.dot(base) / base.norm()
    return s.p1 + base * r

def reflecton(s, p):
    return p + (project(s,p) - p) * 2


def getDistance(a, b):
    return (a-b).abs()

def getDistanceLP(l, p):
    return abs((l.p2-l.p1).cross(p-l.p1)) / ((l.p2-l.p1).abs())

def getDistanceSP(s, p):
    if (s.p2 - s.p1).dot(p-s.p1) < 0:
        return (p-s.p1).abs()
    elif (s.p1 - s.p2).dot(p-s.p2) < 0:
        return (p-s.p2).abs()
    return getDistanceLP(s,p)


def getDistanceSS(s1, s2):
    if intersectS(s1, s2):
        return 0
    return min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2), getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2))



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

def intersect(p1, p2, p3, p4):
    return ccw(p1, p2, p3) *ccw(p1, p2, p4) <=0 and ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0

def intersectS(s1, s2):
    return intersect(s1.p1, s1.p2, s2.p1, s2.p2)


def getCrossPoint(s1, s2):
    base = s2.p2-s2.p1
    a = s1.p1-s2.p1
    b = s1.p2-s2.p1
    
    d1 = abs(a.cross(base))
    d2 = abs(b.cross(base))
    
    t = d1 / (d1+d2)
    return s1.p1 + (s1.p2-s1.p1) * t


def getCrossPointC(c, l):
    pr = project(l, c.c)
    e = (l.p2-l.p1) / (l.p2-l.p1).abs()
    base = (c.r *c.r  - (pr - c.c).norm()) ** 0.5
    return pr - e * base, pr + e * base

def printPoint(p1, p2):
    print(round(p1.x, 8), round(p1.y, 8), round(p2.x, 8), round(p2.y, 8))


def arg(p):
    return math.atan2(p.y ,p.x)

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

def getCrossPointCC(c1, c2):
    d = (c2.c - c1.c).abs()
    a = math.acos((c1.r * c1.r + d*d - c2.r*c2.r) / (2*c1.r*d))
    b = arg(c2.c-c1.c)
    return c1.c + polar(c1.r, b+a), c1.c + polar(c1.r, b-a)


def contains(g, p):
    n = len(g)
    flg = False
    for i in range(n):
        a = g[i] - p
        b = g[(i+1)%n] - p
        if abs(a.cross(b)) < EPS and a.dot(b) < EPS:
            return ON
        if a.y > b.y:
            a,b = b,a
        if a.y < EPS and EPS < b.y and a.cross(b) > EPS:
            flg = not flg
        
    if flg:
        return IN
    else:
        return OUT




n = int(input())
g = []
for i in range(n):
    nums=list(map(int,input().split()))
    g.append(Point(nums[0], nums[1]))

q = int(input())
for i in range(q):
    nums=list(map(int,input().split()))
    p = Point(nums[0], nums[1])
    result = contains(g, p)
    print(result)