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:
#! /usr/bin/env python3

from typing import List, Tuple, Optional, Generator
from math import sqrt, sin, cos, acos, atan2
from enum import IntEnum

EPS = 1e-10


def float_equal(x: float, y: float) -> bool:
    return abs(x - y) < EPS


class PointLocation(IntEnum):
    COUNTER_CLOCKWISE = 1
    CLOCKWISE = -1
    ONLINE_BACK = 2
    ONLINE_FRONT = -2
    ON_SEGMENT = 0

    def is_online(self):
        return self in [PointLocation.ON_SEGMENT,
                        PointLocation.ONLINE_BACK,
                        PointLocation.ONLINE_FRONT]


class Containment(IntEnum):
    OUTSIDE = 0
    ONLINE = 1
    INSIDE = 2


class Point:

    def __init__(self, x: float=0.0, y: float=0.0) -> None:
        self.x = x
        self.y = y

    def __repr__(self) -> str:
        return "Point({}, {})".format(self.x, self.y)

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Point):
            return NotImplemented
        return float_equal(self.x, other.x) and \
            float_equal(self.y, other.y)

    def __add__(self, other: 'Point') -> 'Point':
        return Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other: 'Point') -> 'Point':
        return Point(self.x - other.x, self.y - other.y)

    def __mul__(self, k: float) -> 'Point':
        return Point(self.x * k, self.y * k)

    def __rmul__(self, k: float) -> 'Point':
        return self * k

    def __truediv__(self, k: float) -> 'Point':
        return Point(self.x / k, self.y / k)

    def __lt__(self, other: 'Point') -> bool:
        return self.y < other.y \
            if abs(self.x - other.x) < EPS \
            else self.x < other.x

    @staticmethod
    def polar(a: float, r: float) -> 'Point':
        return Point(a * cos(r), a * sin(r))

    def arg(self) -> float:
        return atan2(self.y, self.x)

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

    def abs(self) -> float:
        return sqrt(self.norm())

    def dot(self, other: 'Point') -> float:
        return self.x * other.x + self.y * other.y

    def cross(self, other: 'Point') -> float:
        return self.x * other.y - self.y * other.x

    def is_orthogonal(self, other: 'Point') -> bool:
        return float_equal(self.dot(other), 0.0)

    def is_parallel(self, other: 'Point') -> bool:
        return float_equal(self.cross(other), 0.0)

    def distance(self, other: 'Point') -> float:
        return (self - other).abs()

    def in_side_of(self, seg: 'Segment') -> bool:
        return seg.vector().dot(
            Segment(seg.p1, self).vector()) >= 0

    def in_width_of(self, seg: 'Segment') -> bool:
        return \
            self.in_side_of(seg) and \
            self.in_side_of(seg.reverse())

    def distance_to_line(self, seg: 'Segment') -> float:
        return \
            abs((self - seg.p1).cross(seg.vector())) / \
            seg.length()

    def distance_to_segment(self, seg: 'Segment') -> float:
        if not self.in_side_of(seg):
            return self.distance(seg.p1)
        if not self.in_side_of(seg.reverse()):
            return self.distance(seg.p2)
        else:
            return self.distance_to_line(seg)

    def location(self, seg: 'Segment') -> PointLocation:
        p = self - seg.p1
        d = seg.vector().cross(p)
        if d > EPS:
            return PointLocation.COUNTER_CLOCKWISE
        if d < -EPS:
            return PointLocation.CLOCKWISE
        if seg.vector().dot(p) < 0.0:
            return PointLocation.ONLINE_BACK
        if seg.vector().norm() < p.norm():
            return PointLocation.ONLINE_FRONT
        return PointLocation.ON_SEGMENT


Vector = Point


class Segment:

    def __init__(self,
                 p1: Optional[Point] = None,
                 p2: Optional[Point] = None) -> None:
        self.p1: Point = Point() if p1 is None else p1
        self.p2: Point = Point() if p2 is None else p2

    def __repr__(self) -> str:
        return "Segment({}, {})".format(self.p1, self.p2)

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Segment):
            return NotImplemented
        return self.p1 == other.p1 and self.p2 == other.p2

    def vector(self) -> Vector:
        return self.p2 - self.p1

    def reverse(self) -> 'Segment':
        return Segment(self.p2, self.p1)

    def length(self) -> float:
        return self.p1.distance(self.p2)

    def is_orthogonal(self, other: 'Segment') -> bool:
        return self.vector().is_orthogonal(other.vector())

    def is_parallel(self, other: 'Segment') -> bool:
        return self.vector().is_parallel(other.vector())

    def projection(self, p: Point) -> Point:
        v = self.vector()
        vp = p - self.p1
        return v.dot(vp) / v.norm() * v + self.p1

    def reflection(self, p: Point) -> Point:
        x = self.projection(p)
        return p + 2 * (x - p)

    def intersects(self, other: 'Segment') -> bool:
        d0: PointLocation = self.p1.location(other)
        d1: PointLocation = self.p2.location(other)
        d2: PointLocation = other.p1.location(self)
        d3: PointLocation = other.p2.location(self)
        return d0 * d1 * d2 * d3 == 0 or \
            (d0 * d1 == -1 and d2 * d3 == -1)

    def intersection(self, other: 'Segment') -> Point:
        a = self.vector()
        b = other.vector()
        c = self.p1 - other.p1
        s = b.cross(c) / a.cross(b)
        return self.p1 + s * a

    def distance_with_segment(self, other: 'Segment') -> float:
        if not self.is_parallel(other) and \
                self.intersects(other):
            return 0
        else:
            return min(
                self.p1.distance_to_segment(other),
                self.p2.distance_to_segment(other),
                other.p1.distance_to_segment(self),
                other.p2.distance_to_segment(self))


Line = Segment


class Circle:

    def __init__(self,
                 c: Optional[Point] = None,
                 r: float=0.0) -> None:
        self.c: Point = Point() if c is None else c
        self.r: float = r

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Circle):
            return NotImplemented
        return self.c == other.c and self.r == other.r

    def __repr__(self) -> str:
        return "Circle({}, {})".format(self.c, self.r)

    def cross_point_line(self, line: Line) -> List[Point]:
        proj = line.projection(self.c)
        dist = self.c.distance_to_line(line)
        tan = sqrt(self.r * self.r - dist * dist)
        u = line.vector() / line.vector().abs()
        return sorted([proj - tan * u, proj + tan * u])

    def cross_point_circle(self, other: 'Circle') -> List[Point]:
        d = (other.c - self.c).abs()
        r1 = self.r
        r2 = other.r
        a = acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d))
        t = (other.c - self.c).arg()
        return sorted([self.c + Vector.polar(self.r, t + a),
                       self.c + Vector.polar(self.r, t - a)])


class Polygon:
    def __init__(self, vertices: List[Point]) -> None:
        self.vertices = vertices
        self.n = len(vertices)

    def sides(self) -> Generator[Segment, None, None]:
        for i in range(self.n):
            yield Segment(self.vertices[i],
                          self.vertices[(i + 1) % self.n])

    def my_contains(self, p: Point) -> Containment:
        ps = Segment(p, Point(100000.0, p.y))
        count = 0

        prev_l = self.vertices[0].location(ps)
        if prev_l.is_online():
            prev_l = self.vertices[-1].location(ps)

        for s in self.sides():
            if p.location(s) == PointLocation.ON_SEGMENT:
                return Containment.ONLINE
            cur_l = s.p2.location(ps)
            if cur_l.is_online() or prev_l == cur_l:
                continue
            if ps.intersects(s):
                count += 1
            prev_l = cur_l

        return Containment.OUTSIDE if count % 2 == 0 \
            else Containment.INSIDE

    def contains(self, p: Point) -> Containment:
        ps = Segment(p, Point(100000.0, p.y))
        count = 0

        for s in self.sides():
            if p.location(s) == PointLocation.ON_SEGMENT:
                return Containment.ONLINE
            if s.p1.y > s.p2.y:
                s = s.reverse()
            l1 = s.p1.location(ps)
            l2 = s.p2.location(ps)
            if l1 != PointLocation.COUNTER_CLOCKWISE and \
                l2 == PointLocation.COUNTER_CLOCKWISE and \
                ps.intersects(s):
                count += 1

        return Containment.OUTSIDE if count % 2 == 0 \
            else Containment.INSIDE

def main() -> None:
    n = int(input())
    points = []
    for _ in range(n):
        x, y = [int(x) for x in input().split()]
        points.append(Point(x, y))
    polygon = Polygon(points)

    q = int(input())
    for _ in range(q):
        x, y = [int(x) for x in input().split()]
        print(int(polygon.contains(Point(x, y))))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# CGL_3_C: Polygon - Polygon-Point Containment

from enum import Enum


class Position(Enum):
    OUTSIDE = 0
    BORDER = 1
    INSIDE = 2


class Polygon:
    def __init__(self, ps):
        self.ps = ps
        self.convex_poligons = divide(ps)

    def position(self, p):
        if p in self.ps:
            return Position.BORDER

        pos = [position(*c, p) for c in self.convex_poligons]
        if all([x == Position.OUTSIDE for x in pos]):
            return Position.OUTSIDE
        elif any([x == Position.INSIDE for x in pos]):
            return Position.INSIDE
        elif len([x for x in pos if x == Position.BORDER]) > 1:
            return Position.INSIDE
        else:
            return Position.BORDER


def divide(ps):
    if len(ps) < 3:
        return []

    p0, p1, p2, *ps = ps
    if not ccw(p0, p1, p2):
        return divide([p1, p2] + ps + [p0])

    for p in ps:
        if position(p0, p1, p2, p) != Position.OUTSIDE:
            return divide([p1, p2] + ps + [p0])

    return [(p0, p1, p2)] + divide([p0, p2] + ps)


def ccw(p0, p1, p2):
    x0, y0 = p0
    x1, y1 = p1
    x2, y2 = p2
    v1 = (x1-x0, y1-y0)
    v2 = (x2-x1, y2-y1)
    return dot(orthogonal(v1), v2) > 0


def dot(v1, v2):
    x1, y1 = v1
    x2, y2 = v2
    return x1 * x2 + y1 * y2


def cross(v1, v2):
    x1, y1 = v1
    x2, y2 = v2
    return x1 * y2 - y1 * x2


def orthogonal(v):
    x, y = v
    return -y, x


def position(p0, p1, p2, p):
    x, y = p
    ps = [p0, p1, p2]
    online = False
    for i in range(3):
        pa = ps[i]
        pb = ps[(i+1) % 3]
        pc = ps[(i+2) % 3]
        xa, ya = pa
        xb, yb = pb
        xc, yc = pc
        vab = (xb-xa, yb-ya)
        vac = (xc-xa, yc-ya)
        vp = (x-xa, y-ya)
        c = cross(vab, vp) * cross(vp, vac)
        if c == 0:
            online = True
        elif c < 0:
            return Position.OUTSIDE

    if online:
        return Position.BORDER
    else:
        return Position.INSIDE


def run():
    g = int(input())

    ps = []
    for _ in range(g):
        x, y = [int(i) for i in input().split()]
        ps.append((x, y))

    poly = Polygon(ps)

    n = int(input())
    for _ in range(n):
        qx, qy = [int(i) for i in input().split()]

        pos = poly.position((qx, qy))
        print(pos.value)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
import math
from typing import Union, Tuple

class Point(object):
    __slots__ = ['x', 'y']

    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: Union[int, float]):
        return Point(self.x * other, self.y * other)

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

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

    def __repr__(self):
        return f"({self.x},{self.y})"


class Vector(Point):
    __slots__ = ['x', 'y', 'pt1', 'pt2']

    def __init__(self, pt1: Point, pt2: Point):
        super().__init__(pt2.x - pt1.x, pt2.y - pt1.y)
        self.pt1 = pt1
        self.pt2 = pt2

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

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

    def arg(self) -> float:
        return math.atan2(self.y, self.x)

    @staticmethod
    def polar(r, theta) -> Point:
        return Point(r * math.cos(theta), r * math.sin(theta))

    def __repr__(self):
        return f"({self.x},{self.y})"


class Segment(Vector):
    __slots__ = ['x', 'y', 'pt1', 'pt2']

    def __init__(self, pt1: Point, pt2: Point):
        super().__init__(pt1, pt2)

    def projection(self, pt: Point)-> Point:
        t = self.dot(Vector(self.pt1, pt)) / self.norm()
        return self.pt1 + self * t

    def reflection(self, pt: Point) -> Point:
        return self.projection(pt) * 2 - pt

    def is_intersected_with(self, other) -> bool:
        if (self.point_geometry(other.pt1) * self.point_geometry(other.pt2)) <= 0\
                and other.point_geometry(self.pt1) * other.point_geometry(self.pt2) <= 0:
            return True
        else:
            return False

    def point_geometry(self, pt: Point) -> int:
        """
        [-2:"Online Back", -1:"Counter Clockwise", 0:"On Segment", 1:"Clockwise",  2:"Online Front"]
        """
        vec_pt1_to_pt = Vector(self.pt1, pt)
        cross = self.cross(vec_pt1_to_pt)
        if cross > 0:
            return -1   # counter clockwise
        elif cross < 0:
            return 1    # clockwise
        else:           # cross == 0
            dot = self.dot(vec_pt1_to_pt)
            if dot < 0:
                return -2    # online back
            else:       # dot > 0
                if self.abs() < vec_pt1_to_pt.abs():
                    return 2    # online front
                else:
                    return 0    # on segment

    def cross_point(self, other) -> Point:
        d1 = abs(self.cross(Vector(self.pt1, other.pt1)))       # / self.abs()
        d2 = abs(self.cross(Vector(self.pt1, other.pt2)))       # / self.abs()
        t = d1 / (d1 + d2)
        return other.pt1 + other * t

    def distance_to_point(self, pt: Point) -> Union[int, float]:
        vec_pt1_to_pt = Vector(self.pt1, pt)
        if self.dot(vec_pt1_to_pt) <= 0:
            return vec_pt1_to_pt.abs()
        vec_pt2_to_pt = Vector(self.pt2, pt)
        if Vector.dot(self * -1, vec_pt2_to_pt) <= 0:
            return vec_pt2_to_pt.abs()
        return (self.projection(pt) - pt).abs()

    def distance_to_segment(self, other) -> Union[int, float]:
        if self.is_intersected_with(other):
            return 0.0
        else:
            return min(
                self.distance_to_point(other.pt1),
                self.distance_to_point(other.pt2),
                other.distance_to_point(self.pt1),
                other.distance_to_point(self.pt2)
            )

    def __repr__(self):
        return f"{self.pt1},{self.pt2}"


class Circle(Point):
    __slots__ = ['x', 'y', 'r']
    def __init__(self, x, y, r):
        super().__init__(x, y)
        self.r = r

    def cross_point_with_circle(self, other) -> Tuple[Point, Point]:
        vec_self_to_other = Vector(self, other)
        vec_abs = vec_self_to_other.abs()
        # if vec_abs > (self.r + other.r):
        #     raise AssertionError
        t = ((pow(self.r, 2) - pow(other.r, 2)) / pow(vec_abs, 2) + 1) / 2
        pt = (other - self) * t
        abs_from_pt = math.sqrt(pow(self.r, 2) - pt.norm())
        inv = Point(vec_self_to_other.y / vec_abs,  - vec_self_to_other.x / vec_abs) * abs_from_pt
        pt_ = self + pt
        return (pt_ + inv), (pt_ - inv)

    def cross_point_with_circle2(self, other) -> Tuple[Point, Point]:
        vec_self_to_other = Vector(self, other)
        vec_abs = vec_self_to_other.abs()
        # if vec_abs > (self.r + other.r):
        #     raise AssertionError

        theta_base_to_other = vec_self_to_other.arg()
        theta_other_to_pt = math.acos((pow(self.r, 2) + pow(vec_abs, 2) - pow(other.r, 2)) / (2 * self.r * vec_abs))

        return self + Vector.polar(self.r, theta_base_to_other + theta_other_to_pt),\
               self + Vector.polar(self.r, theta_base_to_other - theta_other_to_pt)

    def __repr__(self):
        return f"({self.x},{self.y}), {self.r}"


class Polygon(object):
    def __init__(self, vertices):
        self.vertices = vertices
        self.num_vertices = len(vertices)

    def contains_point(self, pt: Point) -> int:
        """
        {0:"not contained", 1: "on a edge", 2:"contained"}
        """
        cross_count = 0
        for i in range(self.num_vertices):
            vec_a = Vector(pt, self.vertices[i])
            vec_b = Vector(pt, self.vertices[(i+1) % self.num_vertices])
            if vec_a.y > vec_b.y:
                vec_a, vec_b = vec_b, vec_a
            dot   = vec_a.dot(  vec_b)
            cross = vec_a.cross(vec_b)

            #print("pt", pt, "vtx", self.vertices[i], self.vertices[(i+1) % self.num_vertices], "vec", vec_a, vec_b, "dot", dot, "cross", cross)
            if math.isclose(cross, 0.0) and dot <= 0:
                return 1        #  on a edge
            elif vec_a.y <= 0.0 < vec_b.y and cross > 0:
                cross_count += 1
        return [0, 2][cross_count % 2]

    def __repr__(self):
        return f"{self.vertices}"


def main():
    num_vertices = int(input())
    polygon_vertices = []
    for i in range(num_vertices):
        pt_x, pt_y = map(int, input().split())
        polygon_vertices.append(Point(pt_x, pt_y))

    polygon = Polygon(polygon_vertices)

    num_queries = int(input())
    for i in range(num_queries):
        pt_x, pt_y = map(int, input().split())
        ret = polygon.contains_point(Point(pt_x, pt_y))
        print(ret)
    return


main()

Submission status: Accepted

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


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


n = int(input())
vertices = [complex(*map(int, input().split())) for _ in range(n)]
edges = [(p0, p1) for p0, p1 in zip(vertices, vertices[1:] + [vertices[0]])]

q = int(input())
while q:
    q -= 1
    p = complex(*map(int, input().split()))
    counter = 0
    for p0, p1 in edges:
        a, b = p0 - p, p1 - p
        if a.imag > b.imag:
            a, b = b, a
        crs = cross(a, b)
        if a.imag <= 0 and 0 < b.imag and crs < 0:
            counter += 1
        if crs == 0 and dot(a, b) <= 0:
            print(1)
            break
    else:
        print(2 if counter % 2 else 0)

Submission status: Accepted

Solution code:
import math

EPS = 1e-10

def equals(a, b):
    return abs(a - b) < EPS


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

    def __add__(self, p):
        return Point(self.x + p.x, self.y + p.y)

    def __sub__(self, p):
        return Point(self.x - p.x, self.y - p.y)

    def __mul__(self, a):
        return Point(self.x * a, self.y * a)

    def __rmul__(self, a):
        return self * a

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

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

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

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

    def __eq__(self, p):
        return equals(self.x, p.x) and equals(self.y, p.y)


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 contains(g, p):
    n = len(g)
    isIn = 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:
            isIn = not isIn
    if isIn:
        return 2
    else:
        return 0


if __name__ == '__main__':
    n = int(input())
    g = []
    for i in range(n):
        x, y =  [int(v) for v in input().split()]
        g.append(Point(x, y))

    q = int(input())
    ans = []
    for i in range(q):
        x, y =  [int(v) for v in input().split()]
        ans.append(contains(g, Point(x, y)))

    for v in ans:
        print(v)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

def in_sec(a, b, c):
    return min(a, b) <= c <= max(a, b)

g = input()
lst = []
for loop in range(g):
    x, y = map(int, raw_input().split())
    lst.append((x, y))
lst += lst[:1]

n = input()
for loop in range(n):
    x, y = map(int, raw_input().split())
    flag = False
    for i in range(g):
        x1, y1 = lst[i]
        x2, y2 = lst[i + 1]
        if (x1 - x) * (y2 - y) == (x2 - x) * (y1 - y) and \
            (x1 - x) * (x2 - x) <= 0 and (y1 - y) * (y2 - y) <= 0:
            print 1
            flag = True
            break
    if flag:
        continue
    cnt = 0
    for i in range(g):
        x1, y1 = [x + 1, y + 10000000]
        x2, y2 = lst[i]
        x3, y3 = lst[i + 1]
        a1, b1, c1 = [y1 - y, x - x1, x * (y1 - y) - y * (x1 - x)]
        a2, b2, c2 = [y3 - y2, x2 - x3, x2 * (y3 - y2) - y2 * (x3 - x2)]
        det = a1 * b2 - b1 * a2
        if in_sec(x2 * det, x3 * det, c1 * b2 - c2 * b1) \
            and in_sec(y2 * det, y3 * det, c2 * a1 - c1 * a2) \
            and y < float(c2 * a1 - c1 * a2) / det:
            cnt += 1
    print (cnt % 2) * 2