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 sys
from operator import itemgetter, attrgetter
from itertools import starmap
import cmath
from math import isinf, sqrt, acos, atan2
readline = sys.stdin.readline
EPS = 1e-9
ONLINE_FRONT = -2
CLOCKWISE = -1
ON_SEGMENT = 0
COUNTER_CLOCKWISE = 1
ONLINE_BACK = 2
class Circle(object):
    __slots__ = ('c', 'r')
    def __init__(self, c, r):
        self.c = c
        self.r = r
class Segment(object):
    __slots__ = ('fi', 'se')
    def __init__(self, fi, se):
        self.fi = fi
        self.se = se
Line = Segment
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 norm(base):
    return abs(base) ** 2
def project(s, p2):
    base = s.fi - s.se
    r = dot(p2 - s.fi, base) / norm(base)
    return s.fi + base * r
def reflect(s, p):
    return p + (project(s, p) - p) * 2.0
def ccw(p1, p2, p3):
    a = p2 - p1
    b = p3 - p1
    if cross(a, b) > EPS: return 1
    if cross(a, b) < -EPS: return -1
    if dot(a, b) < -EPS: return 2
    if norm(a) < norm(b): return -2
    return 0
def intersect4(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 intersect2(s1, s2):
    return intersect4(s1.fi, s1.se, s2.fi, s2.se)
def getDistance(a, b):  return abs(a - b)
def getDistanceLP(l, p):
    return abs(cross(l.se - l.fi, p - l.fi) / abs(l.se - l.fi))
def getDistanceSP(s, p):
    if dot(s.se - s.fi, p - s.fi) < 0.0: return abs(p - s.fi)
    if dot(s.fi - s.se, p - s.se) < 0.0: return abs(p - s.se)
    return getDistanceLP(s, p)
def getDistances(s1, s2):
    if intersect2(s1, s2): return 0.0
    return min(getDistanceSP(s1, s2.fi), getDistanceSP(s1, s2.se),
               getDistanceSP(s2, s1.fi), getDistanceSP(s2, s1.se))
def getCrossPoint(s1, s2):
	base = s2.se - s2.fi
	d1 = abs(cross(base, s1.fi - s2.fi))
	d2 = abs(cross(base, s1.se - s2.fi))
	t = d1 / (d1 + d2)
	return s1.fi + (s1.se - s1.fi) * t
def getCrossPointsCL(c, l):
    pr = project(l, c.c)
    e = (l.se - l.fi) / abs(l.se - l.fi)
    base = sqrt(c.r * c.r - norm(pr - c.c))
    return Segment(*sorted((pr + e * base, pr - e * base)), key=attrgetter('real', 'imag'))
def getCrossPointsCC(c1, c2):
    d = abs(c1.c - c2.c)
    a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2.0 * c1.r * d))
    t = cmath.phase(c2.c - c1.c)
    return Segment(*sorted((c1.c + cmath.rect(c1.r, t + a), c1.c + cmath.rect(c1.r, t - a)), key=attrgetter('real', 'imag')))
def contains(g, p):
    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.imag > b.imag: a, b = b, a
        if a.imag < EPS and EPS < b.imag and cross(a, b) > EPS: x = not x
    return 2 if x else 0
n = int(readline())
pg = tuple(complex(*map(int, readline().split())) for _ in [0] * n)
q = int(readline())
for _ in [0] * q:
    x, y = map(int, readline().split())
    print(contains(pg, complex(x, y)))

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter, attrgetter
from itertools import starmap
import cmath
from math import isinf, sqrt, acos, atan2
readline = sys.stdin.readline
EPS = 1e-9
ONLINE_FRONT = -2
CLOCKWISE = -1
ON_SEGMENT = 0
COUNTER_CLOCKWISE = 1
ONLINE_BACK = 2
class Circle(object):
    __slots__ = ('c', 'r')
    def __init__(self, c, r):
        self.c = c
        self.r = r
class Segment(object):
    __slots__ = ('fi', 'se')
    def __init__(self, fi, se):
        self.fi = fi
        self.se = se
Line = Segment
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 norm(base):
    return abs(base) ** 2
def project(s, p2):
    base = s.fi - s.se
    r = dot(p2 - s.fi, base) / norm(base)
    return s.fi + base * r
def reflect(s, p):
    return p + (project(s, p) - p) * 2.0
def ccw(p1, p2, p3):
    a = p2 - p1
    b = p3 - p1
    if cross(a, b) > EPS: return 1
    if cross(a, b) < -EPS: return -1
    if dot(a, b) < -EPS: return 2
    if norm(a) < norm(b): return -2
    return 0
def intersect4(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 intersect2(s1, s2):
    return intersect4(s1.fi, s1.se, s2.fi, s2.se)
def getDistance(a, b):  return abs(a - b)
def getDistanceLP(l, p):
    return abs(cross(l.se - l.fi, p - l.fi) / abs(l.se - l.fi))
def getDistanceSP(s, p):
    if dot(s.se - s.fi, p - s.fi) < 0.0: return abs(p - s.fi)
    if dot(s.fi - s.se, p - s.se) < 0.0: return abs(p - s.se)
    return getDistanceLP(s, p)
def getDistances(s1, s2):
    if intersect2(s1, s2): return 0.0
    return min(getDistanceSP(s1, s2.fi), getDistanceSP(s1, s2.se),
               getDistanceSP(s2, s1.fi), getDistanceSP(s2, s1.se))
def getCrossPoint(s1, s2):
	base = s2.se - s2.fi
	d1 = abs(cross(base, s1.fi - s2.fi))
	d2 = abs(cross(base, s1.se - s2.fi))
	t = d1 / (d1 + d2)
	return s1.fi + (s1.se - s1.fi) * t
def getCrossPointsCL(c, l):
    pr = project(l, c.c)
    e = (l.se - l.fi) / abs(l.se - l.fi)
    base = sqrt(c.r * c.r - norm(pr - c.c))
    return Segment(*sorted((pr + e * base, pr - e * base)), key=attrgetter('real', 'imag'))
def getCrossPointsCC(c1, c2):
    d = abs(c1.c - c2.c)
    a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2.0 * c1.r * d))
    t = cmath.phase(c2.c - c1.c)
    return Segment(*sorted((c1.c + cmath.rect(c1.r, t + a), c1.c + cmath.rect(c1.r, t - a)), key=attrgetter('real', 'imag')))
def contains(g, p):
    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.imag > b.imag: a, b = b, a
        if a.imag < EPS and EPS < b.imag and cross(a, b) > EPS: x = not x
    return 2 if x else 0
n = int(readline())
pg = tuple(complex(*map(int, readline().split())) for _ in [0] * n)
q = int(readline())
for _ in [0] * q:
    print(contains(pg, complex(*map(float, readline().split()))))

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter, attrgetter
from itertools import starmap
import cmath
from math import isinf, sqrt, acos, atan2
readline = sys.stdin.readline
EPS = 1e-9
ONLINE_FRONT = -2
CLOCKWISE = -1
ON_SEGMENT = 0
COUNTER_CLOCKWISE = 1
ONLINE_BACK = 2
class Circle(object):
    __slots__ = ('c', 'r')
    def __init__(self, c, r):
        self.c = c
        self.r = r
class Segment(object):
    __slots__ = ('fi', 'se')
    def __init__(self, fi, se):
        self.fi = fi
        self.se = se
Line = Segment
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 norm(base):
    return abs(base) ** 2
def project(s, p2):
    base = s.fi - s.se
    r = dot(p2 - s.fi, base) / norm(base)
    return s.fi + base * r
def reflect(s, p):
    return p + (project(s, p) - p) * 2.0
def ccw(p1, p2, p3):
    a = p2 - p1
    b = p3 - p1
    if cross(a, b) > EPS: return 1
    if cross(a, b) < -EPS: return -1
    if dot(a, b) < -EPS: return 2
    if norm(a) < norm(b): return -2
    return 0
def intersect4(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 intersect2(s1, s2):
    return intersect4(s1.fi, s1.se, s2.fi, s2.se)
def getDistance(a, b):  return abs(a - b)
def getDistanceLP(l, p):
    return abs(cross(l.se - l.fi, p - l.fi) / abs(l.se - l.fi))
def getDistanceSP(s, p):
    if dot(s.se - s.fi, p - s.fi) < 0.0: return abs(p - s.fi)
    if dot(s.fi - s.se, p - s.se) < 0.0: return abs(p - s.se)
    return getDistanceLP(s, p)
def getDistances(s1, s2):
    if intersect2(s1, s2): return 0.0
    return min(getDistanceSP(s1, s2.fi), getDistanceSP(s1, s2.se),
               getDistanceSP(s2, s1.fi), getDistanceSP(s2, s1.se))
def getCrossPoint(s1, s2):
	base = s2.se - s2.fi
	d1 = abs(cross(base, s1.fi - s2.fi))
	d2 = abs(cross(base, s1.se - s2.fi))
	t = d1 / (d1 + d2)
	return s1.fi + (s1.se - s1.fi) * t
def getCrossPointsCL(c, l):
    pr = project(l, c.c)
    e = (l.se - l.fi) / abs(l.se - l.fi)
    base = sqrt(c.r * c.r - norm(pr - c.c))
    return Segment(*sorted((pr + e * base, pr - e * base)), key=attrgetter('real', 'imag'))
def getCrossPointsCC(c1, c2):
    d = abs(c1.c - c2.c)
    a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2.0 * c1.r * d))
    t = cmath.phase(c2.c - c1.c)
    return Segment(*sorted((c1.c + cmath.rect(c1.r, t + a), c1.c + cmath.rect(c1.r, t - a)), key=attrgetter('real', 'imag')))
def contains(g, p):
    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.imag > b.imag: a, b = b, a
        if a.imag < EPS and EPS < b.imag and cross(a, b) > EPS: x = not x
    return 2 if x else 0
n = int(readline())
pg = tuple(complex(*map(int, readline().split())) for _ in [0] * n)
q = int(readline())
for _ in [0] * q:
    print(contains(pg, complex(*map(int, readline().split()))))

Submission status: Accepted

Solution code:
# Aizu Problem CGL_3_C: Polygon-Point-Containment
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def cross_product_test(A, B, C):
    if A[1] == B[1] == C[1]:
        if B[0] <= A[0] <= C[0] or C[0] <= A[0] <= B[0]:
            return 0
        else:
            return 1
    if B[1] > C[1]:
        B, C = C[:], B[:]
    if A[1] == B[1] and A[0] == B[0]:
        return 0
    if A[1] <= B[1] or A[1] > C[1]:
        return 1
    delta = (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])
    if delta > 0:
        return -1
    elif delta < 0:
        return 1
    else:
        return 0

def point_in_polygon(polygon, point):
    t = -1
    polygon.append(polygon[0])
    for i in range(len(polygon) - 1):
        t *= cross_product_test(point, polygon[i], polygon[i+1])
    return t

N = int(input())
P = [[int(_) for _ in input().split()] for __ in range(N)]
Q = int(input())
for q in range(Q):
    x, y = [int(_) for _ in input().split()]
    print(point_in_polygon(P, [x, y]) + 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_C&lang=jp

"""
import sys
from math import sqrt, atan2, acos, sin, cos
from sys import stdin
input = stdin.readline


class Point(object):
    epsilon = 1e-10

    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        else:
            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(other * self.x, other * self.y)

    def __truediv__(self, other):
        return Point(self.x / other, self.y / other)

    def __lt__(self, other):
        if self.x == other.x:
            return self.y < other.y
        else:
            return self.x < other.x

    def __eq__(self, other):
        from math import fabs
        if fabs(self.x - other.x) < Point.epsilon and fabs(self.y - other.y) < Point.epsilon:
            return True
        else:
            return False

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

    def __abs__(self):
        return sqrt(self.norm())

    def ccw(self, p0, p1):
        # ??????2???(p0, p1)?????????????????????????????????????????¢????????????
        a = Vector(p1 - p0)
        b = Vector(self - p0)
        if Vector.cross(a, b) > Point.epsilon:
            return 1 # 'COUNTER_CLOCKWISE'
        elif Vector.cross(a, b) < -Point.epsilon:
            return -1 # 'CLOCKWISE'
        elif Vector.dot(a, b) < -Point.epsilon:
            return 2 # 'ONLINE_BACK'
        elif a.norm() < b.norm():
            return -2 # 'ONLINE_FRONT'
        else:
            return 0 # 'ON_SEGMENT'

    def project(self, s):
        # ??????(Point)????????????s??????????????????????????????????????§?¨?(?°???±)????±???????
        base = Vector(s.p2 - s.p1)
        a = Vector(self - s.p1)
        r = Vector.dot(a, base)
        r /= base.norm()
        return s.p1 + base * r

    def reflect(self, s):
        # ??????s???????§°?????¨?????????????????¨???????§°??????????????§?¨?(????°?)????±???????
        proj = self.project(s)
        return self + (proj - self)*2

    def distance(self, s):
        # ????????¨??????s????????¢????¨??????????
        if Vector.dot(s.p2-s.p1, self-s.p1) < 0.0:
            return abs(self - s.p1)
        if Vector.dot(s.p1-s.p2, self-s.p2) < 0.0:
            return abs(self - s.p2)
        return abs(Vector.cross(s.p2-s.p1, self-s.p1) / abs(s.p2-s.p1))


class Vector(Point):
    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        elif isinstance(x, Point):
            self.x = x.x
            self.y = x.y
        else:
            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)

    def __mul__(self, other):
        return Vector(other * self.x, other * self.y)

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


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

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

    @classmethod
    def is_orthogonal(cls, a, b):
        return Vector.dot(a, b) == 0.0

    @classmethod
    def is_parallel(cls, a, b):
        return Vector.cross(a, b) == 0.0


class Segment(object):
    def __init__(self, p1=Point(), p2=Point()):
        if isinstance(p1, Point):
            self.p1 = p1
            self.p2 = p2
        elif isinstance(p1, tuple):
            self.p1 = Point(p1[0], p1[1])
            self.p2 = Point(p2[0], p2[1])

    def intersect(self, s):
        # ????????¨??????????????????????????????????????????????????????
        ans1 = s.p1.ccw(self.p1, self.p2) * s.p2.ccw(self.p1, self.p2)
        ans2 = self.p1.ccw(s.p1, s.p2) * self.p2.ccw(s.p1, s.p2)
        return ans1 <= 0 and ans2 <= 0

    def cross_point(self, s):
        # ????????¨??????????????????????????????????????§?¨?????±???????
        base = s.p2 - s.p1
        d1 = abs(Vector.cross(base, self.p1-s.p1))
        d2 = abs(Vector.cross(base, self.p2-s.p1))
        t = d1 / (d1 + d2)
        return self.p1 + (self.p2 - self.p1) * t

    def distance(self, s):
        # ????????¨?????????????????????????????¢????±???????
        if self.intersect(s):
            return 0.0
        d1 = s.p1.distance(self)
        d2 = s.p2.distance(self)
        d3 = self.p1.distance(s)
        d4 = self.p2.distance(s)
        return min(d1, d2, d3, d4)


    @classmethod
    def is_orthogonal(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_orthogonal(a, b)

    @classmethod
    def is_parallel(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_parallel(a, b)


class Line(Segment):
    pass


class Cirle(object):
    def __init__(self, x, y=Point(), r=1.0):
        if isinstance(x, Point):
            self.c = x
            self.r = y
        elif isinstance(x, tuple):
            self.c = Point(x[0], x[1])
            self.r = r

    def cross_points(self, s):
        if isinstance(s, Segment):
            pr = self.c.project(s)
            e = (s.p2 - s.p1) / abs(s.p2 - s.p1)
            base = sqrt(self.r * self.r - (pr - self.c).norm())
            return pr + e * base, pr - e * base
        elif isinstance(s, Cirle):
            c2 = s
            d = abs(self.c - c2.c)
            a = acos((self.r * self.r + d * d - c2.r * c2.r) / (2 * self.r * d))
            t = atan2(c2.c.y - self.c.y, c2.c.x - self.c.x)
            temp1 = Point(cos(t+a)*self.r, sin(t+a)*self.r)
            temp2 = Point(cos(t-a)*self.r, sin(t-a)*self.r)
            return self.c + temp1, self.c + temp2


def contains(polygon, p):
    n = len(polygon)
    x = False
    for i in range(n):
        a = polygon[i] - p
        b = polygon[(i+1)%n] - p
        if abs(Vector.cross(a, b)) < Point.epsilon and Vector.dot(a, b) < Point.epsilon:
            return 1
        if a.y > b.y:
            temp = a
            a = b
            b = temp
        if a.y < Point.epsilon and Point.epsilon < b.y and Vector.cross(a, b) > Point.epsilon:
            x = not x
    return 2 if x else 0


def main(args):
    n = int(input())
    polygon = []
    for _ in range(n):
        x, y = map(int, input().split())
        polygon.append(Point(x, y))
    q = int(input())
    for _ in range(q):
        x, y = map(int, input().split())
        result = contains(polygon, Point(x, y))
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
n = int(input())
g = []
for i in range(n):
    g.append([int(i) for i in input().split()])
q = int(input())
EPS = 0.001
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)) < EPS and dot(a, b) < EPS: 
            return 1
        if a[1] > b[1]:
            a,b=b,a
        if a[1] < EPS and EPS < b[1] and cross(a,b) > EPS:
            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: Accepted

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

Solution code:
compare=lambda a,b: a.real<b.real if a.real!=b.real else a.imag<b.imag
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:
#!/usr/bin/python
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:
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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from sys import stdin
input = stdin.readline
import collections
import math


__author__ = "Hamukichi (Nombiri)"
__copyright__ = "Copyright 2015, Hamukichi (Nombiri)"
__version__ = "0.1.0"
__date__ = "2015-11-29"
__licence__ = "MIT License"

eps = 10E-4

def is_equal(v1, v2):
    d = abs(v1 - v2)
    if d < eps:
        return True
    return False

class Vector2(collections.namedtuple("Vector2", "x y")):
    """Class for representing a two-dimensional vector.
    :param x: The x component of the vector.
    :type x: float
    :param y: The y component of the vector.
    :type y: float
    """

    __slots__ = ()

    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, other):  # cross product
        return self.x * other.y - self.y * other.x

    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 dotproduct(self, other):
        """Returns the dot product of this vector and the given vector.
        :param other: The second vector.
        """

        return self.x * other.x + self.y * other.y

lines = stdin.readlines()
n = int(lines[0])
q = int(lines[n+1])

v_set = []
for i in range(1, n+1):
    v_set.append(Vector2(*list(map(int, lines[i].split()))))

def is_involed(p):

    counter = 0

    for i in range(n):
        g_i = v_set[i-1]
        g_in = v_set[i]
        if g_i.y <= g_in.y:
            a = g_i - p
            b = g_in - p
        else:
            b = g_i - p
            a = g_in - p

        if  a * b > 0:
            if a.y  <= 0 < b.y :
                counter += 1
        elif a * b == 0:
            if a.dotproduct(b) <= 0:
                return -1

    return counter

for k in range(q):
    p = Vector2(*list(map(int, lines[n+2+k].split())))
    t = is_involed(p)
    if t < 0:
        print(1)
    elif t % 2 == 0:
        print(0)
    else:
        print(2)

Submission status: Accepted

Solution code:
import math

class Vector:
    def __init__(self,x,y):
        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)
    
    def __mul__(self,scalar):
        return Vector(self.x*scalar,self.y*scalar)
    def __rmul__(self, scalar):
        return Vector(self.x*scalar,self.y*scalar)
    
   
    def __repr__(self):
        return str([self.x,self.y])
        
    def norm_2(self):
        return dot(self,self)
    
    def norm(self):
        return math.sqrt(self.norm_2())
    
def v_sum(v1,v2):
    return Vector(v1.x+v2.x,v1.y+v2.y) 
def scalar_multi(k,v):
    return Vector(k*v.x,k*v.y)
def v_diff(v1,v2):
    return v_sum(v1,scalar_multi(-1,v2))
    
def dot(vector1,vector2):
    return vector1.x*vector2.x+vector1.y*vector2.y

def cross(vector1,vector2):
    return vector1.x*vector2.y-vector1.y*vector2.x

def is_crossed(p,far_point,s,t):
    a = far_point-p
    b = t-s
    v = s-p
    w = t-p
    x = p-s
    y = far_point-s
    if cross(a,v)*cross(a,w)<0 and cross(b,x)*cross(b,y)<0:
        return 0#'crossed on the edge'
    if cross(b,x) == 0 and 0<=dot(b,x)<=b.norm_2():
        return 1#'p on segment'
    if (cross(a,v)== 0 and 0<=dot(a,v)<=a.norm_2()) or (cross(a,w)==0 and 0<=dot(a,w)<=a.norm_2()):
        return 2#'crossed on the corner'
    return 3#not crossed

def polygon_content(point):
    insec_count = 0
    
    
    far_point = Vector(21001,21011) + point
    
    for i in range(n):
        judge = is_crossed(point,far_point,p[i-1],p[i])
        if judge==0:
            insec_count+=1
        elif judge==1:
            return 1
        elif judge==2:
            insec_count+=0.5
        
    if insec_count==0:
        return 0
    elif insec_count%2==0:
            return 0
    else:
        return 2

n = int(input())
p = []
for i in range(n):
    x,y = map(int,input().split())
    p.append(Vector(x,y))

q = int(input())
for i in range(q):
    x,y = map(int,input().split())
    print(polygon_content(Vector(x,y)))

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_3_C
# 本の説明を図に書き出してみるとよく理解できる。
from math import sqrt


class Vector:
    def __init__(self, ls):
        '''
        ls ... list
        '''
        self.vec = ls

    def __len__(self):
        return len(self.vec)

    def __getitem__(self, idx):
        return self.vec[idx]

    def __repr__(self):
        return f'Vector({self.vec})'

    def add(self, vec):
        '''
        vec ... vector class
        '''
        assert len(self) == len(vec)
        ret = [a + b for a, b in zip(self.vec, vec.vec)]
        return Vector(ret)

    def sub(self, vec):
        '''
        vec ... vector class
        '''
        assert len(self) == len(vec)
        ret = [a - b for a, b in zip(self.vec, vec.vec)]
        return Vector(ret)

    def mul(self, vec):
        '''
        vec ... vector class
        '''
        assert len(self) == len(vec)
        ret = [a * b for a, b in zip(self.vec, vec.vec)]
        return Vector(ret)

    def norm(self):
        tmp = sum([x * x for x in self.vec])
        return sqrt(tmp)


def norm(vec):
    '''
    vec ... Vector class
    '''
    return vec.norm()


def cross(a, b):
    '''
    Outer product for 2d
    a,b ... Vector class
    '''
    assert len(a) == 2 and len(b) == 2
    first = a[0] * b[1]
    second = a[1] * b[0]
    return first - second


def dot(a, b):
    return sum(a.mul(b))


EPS = 1e-10


def contains(G, p):
    '''
    Gは多角形を表すリストで、今回ならばvectorが中に並んでいることとする
    pは内容しているか判別したい点で、Vectorで表す

    pが多角形Gの辺上にあれば1
    pが多角形Gに内包されていれば2
    それ以外は0をreturnする
    '''
    is_contain = False  # 内包してるか
    for i in range(len(G)):
        a = G[i].sub(p)
        b = G[(i + 1) % len(G)].sub(p)  # i+1が0に戻るようにこのような形式にしている。
        # もしpがG[i]とG[i+1]の線分上にある場合は即座に1をreturnします
        if abs(cross(a, b)) < EPS and dot(a, b) < EPS:
            # 外積が0→a,bが同一直線上
            # かつ 内積が負→a,bは逆を向いている
            # ならばpは線分上に存在する
            return 1
        # 内包を判定する。前処理として、yの座標によってa,bを入れ替える
        if a[1] > b[1]:  # aの方のy座標を小さくしたい
            a, b = b, a
        if a[1] < EPS and b[1] > EPS and cross(a, b) > EPS:  # 実際に判別する
            is_contain = (not is_contain)
    return (0, 2)[is_contain]  # 書き方キモいけど三項演算子の短い書き方


# load data
N = int(input())
G = []
for _ in range(N):
    g = Vector(list(map(int, input().split())))
    G.append(g)

# answer query
Q = int(input())
for _ in range(Q):
    p = Vector(list(map(int, input().split())))
    print(contains(G, p))