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
EPS=1e-14

#点类
class Point():

    def __init__(self,x,y):
        self.x=x
        self.y=y
    
    def __sub__(self,p):
        return Point(self.x - p.x, self.y - p.y);
    def __add__(self,p):
        return Point(self.x + p.x, self.y + p.y)
           
    def __mul__(self,a): #a: scalar
        return Point(self.x * a, self.y * a)
    def __truediv__(self,a): #a: scalar
        return Point(self.x / a, self.y / a)
   
    def __str__(self):
       return  str(self.x)+','+str(self.y)
    def __repr__(self):
        return  'Point('+str(self.x)+','+str(self.y)+')'
    
    def __lt__(self, other):    
        if self.y-other.y==0:
            return self.x<other.x
        else:
            return self.y<other.y
            
    def __eq__(self, other):    
        return abs(self.x-other.x)<EPS and  abs(self.y-other.y)<EPS


# 线段类
class Segment():
    def __init__(self,p1, p2):
        self.p1=p1
        self.p2=p2
    def __str__(self):
        return  'segment:('+str(self.p1)+';'+str(self.p2)+')'
    def __repr__(self):
        return  'segment:('+str(self.p1)+';'+str(self.p2)+')'


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

    def __str__(self):
       return  'Circle:(center point: '+str(self.c)+'; radius: '+str(self.r)+')'
    def __repr__(self):
       return  'Circle:(center point: '+str(self.c)+'; radius: '+str(self.r)+')'
   
    
#定义多边形
class Polygon():
    def __init__(self,ps=[]):
        self.ps=ps
        self.size=len(ps)
  
    def __getitem__(self, i):#iter override 
        return self.ps[i]  
    def __setitem__(self,i,p): 
        self.ps[i]=p               
    def __iter__(self):     
        return self.ps  
    
    def addpoint(self,i,p):
        self.ps.insert(i,p)
        self.size+=1
    def delpoint(self,i):
        self.size-=1
        return self.ps.pop(i)
    def sortYX(self):
        self.ps.sort()
        #self.ps.sort(key=attrgetter('y','x'))
    def __str__(self):
       return  'Polygon:'+str(tuple(self.ps))
    def __repr__(self):
       return  'Polygon:'+str(tuple(self.ps))
        
    def __len__(self):
        return len(self.ps)
    def __eq__(self, other):  
         return self.ps==other.ps
    
    def draw(self):
      
       turtle.screensize(800,800,"black")
       #turtle.setup(width=0.9,height=0.9)
       turtle.title("Polygon convex hull")
       turtle.setworldcoordinates(-400,-400,400,400) 

       #print(turtle.screensize())
       #mywin = turtle.Screen()    
       #mywin.   
       t=turtle.Turtle() 
       #mywin=turtle.Screen()
       
       t.pencolor("red")
       for pt in self.ps:
           t.goto(pt.x,pt.y)
           t.dot(10,'white')
       
 

#***************************点、向量****************************

#向量的模的平方
def norm(p):  
    return p.x * p.x + p.y * p.y


#向量P的长度
def length(p):
    return math.sqrt(p.x * p.x + p.y * p.y)


# 向量的(点)内积, dot(a,b)=|a|*|b|*cos(a,b) (从a,到b的角)
# =============================================================================
# r=dot(a,b),得到矢量a和b的点积，如果两个矢量都非零矢量  
# r<0：两矢量夹角为钝角； 
# r=0：两矢量夹角为直角； 
# r>0：两矢量夹角为锐角  
# =============================================================================
def dot(a, b) :
    return a.x * b.x + a.y * b.y



# =============================================================================
# # 向量的（叉）外积 cross(a,b)=|a||b|*sin(a,b) (从a,到b的角)由a,b构成的平行四边的面积
# r=cross(a,b),得到向量a和向量b的叉积  
# r>0：b在矢量a的逆时针方向；  
# r=0：a,b 平行共线；  
# r<0：b在向量a的顺时针方向 
# =============================================================================
def cross( a, b) :
    return a.x * b.y - a.y * b.x

# 点p在线段s上的投影
def project(s, p):
    base = s.p2 - s.p1
    r = dot(p - s.p1, base) / norm(base)
    return s.p1 + base * r 


# 点a到点b的距离
def getDistance(a, b) :
    return length(a - b)

# 线段l和点p的距离
def getDistanceLP(l, p) :
    return abs( cross(l.p2 - l.p1, p - l.p1) / length(l.p2 - l.p1) )

#getDistanceLP(s3, p7)
    
#线段s与点p的距离
def getDistanceSP(s, p) :
    if (dot(s.p2 - s.p1, p - s.p1) < 0.0):
        return length(p - s.p1)
    if (dot(s.p1 - s.p2, p - s.p2) < 0.0):
        return length(p - s.p2)
    return getDistanceLP(s, p)

#print(getDistanceLP(s3, Point(5,5)))
#print(getDistanceSP(s3, Point(5,5)))


#*************************线段********************************/
# 线段s1，s2是否正交 <==> 内积为0
def isOrthogonalSG(s1, s2) :
    return abs(dot(s1.p2 - s1.p1, s2.p2 - s2.p1))<EPS


# 线段s1，s2是否平行 <==> 叉积为0
def isParallelLN(s1,s2) :
    return abs(cross(s1.p2 - s1.p1, s2.p2 - s2.p1))<0




# 逆时针方向ccw（Counter-Clockwise）
COUNTER_CLOCKWISE = 1;
CLOCKWISE = -1;
ONLINE_BACK = -2;
ONLINE_FRONT = 2;
ON_SEGMENT = 0;

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 (norm(a) < norm(b)):
        return ONLINE_FRONT
    
    return ON_SEGMENT;


def toleft(p0,p1,p2):
    a = p1 - p0
    b = p2 - p0  
    tmp=cross(a,b)
    if tmp > EPS:
        return 1
    elif abs(tmp)<EPS and norm(a)<=norm(b):
        return 2  #共线，p2在p0p1的右延长线上
    elif abs(tmp)<EPS and norm(a)>norm(b):
        return -2  #共线，p2在p0p1的left延长线上    
    else:
        return -1


#以线段s为对称轴与点p成线对称的点
def reflect(s, p) :
    return p + (project(s, p) - p) * 2.0



#判断线段s1和s2是否相交
def intersectSG(s1, s2) :
    return intersectP4(s1.p1, s1.p2, s2.p1, s2.p2)


# 线段s1和线段s2的距离
def getDistanceSG(s1, s2) :
    # 相交
    if (intersectSG(s1, s2)):
        return 0.0
    return min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2),\
        getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2))

# 判断线段p1p2和线段p3p4是否相交
def intersectP4(p1, p2, p3, p4) :
    return ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 and \
            ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0


# 线段s1与线段s2的交点
def getCrossPoint(s1,s2) :
    base = s2.p2 - s2.p1;
    d1 = abs(cross(base, s1.p1 - s2.p1));
    d2 = abs(cross(base, s1.p2 - s2.p1));
    if d1+d2==0:
        return s2.p1
    t = d1 / (d1 + d2);
    return s1.p1 + (s1.p2 - s1.p1) * t;


# 圆c和直线l的交点
def getCrossPointsCL(c, l) :
    pr = project(l, c.c);
    e = (l.p2 - l.p1) / length(l.p2 - l.p1)
    base = math.sqrt(c.r * c.r - norm(pr - c.c))
    return (pr - e * base),(pr + e * base)


# 圆c1和圆c2的交点
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 getCrossPointsCC(c1, c2): 
    d = length(c1.c - c2.c)
    #余弦定理
    if d<EPS:
        print ("two circels with the same center point")
        return -1
    a = math.acos((c1.r * c1.r + d * d - c2.r * c2.r) / (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))


#***************************多边形****************************/
# 点的内包
 # IN 2
  #  ON 1
   # OUT 0

def contains(g, p) : # polygon is not necessarily convex.
    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)) ==0 and dot(a, b) < 0):
            return 1
        if (a.y > b.y):
            a,b=b,a
        if (a.y <= 0 and 0 < b.y and cross(a, b) > 0):
            x = not x
     
    if x==True:
        return 2 #in
    else:
        return 0 #out

n=int(input())
g=[]
for i in range(0,n):
    s= [int(x) for x in input().split()]
    p0=Point(s[0],s[1])
    g.append(p0)

q=int(input())
for i in range(0,q):
    s= [int(x) for x in input().split()]
    pa=Point(s[0],s[1])
    rt=contains(g, pa)
    print(rt)

Submission status: Wrong Answer

Solution code:
def point_in_poly(x,y,poly):

   # check if point is a vertex
   if (x,y) in poly: return 1

   # check if point is on a boundary
   for i in range(len(poly)):
      p1 = None
      p2 = None
      if i==0:
         p1 = poly[0]
         p2 = poly[1]
      else:
         p1 = poly[i-1]
         p2 = poly[i]
      if p1[1] == p2[1] and p1[1] == y and x > min(p1[0], p2[0]) and x < max(p1[0], p2[0]):
         return 1
      
   n = len(poly)
   inside = False

   p1x,p1y = poly[0]
   for i in range(n+1):
      p2x,p2y = poly[i % n]
      if y > min(p1y,p2y):
         if y <= max(p1y,p2y):
            if x <= max(p1x,p2x):
               if p1y != p2y:
                  xints = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
               if p1x == p2x or x <= xints:
                  inside = not inside
      p1x,p1y = p2x,p2y

   if inside: return 2
   else: return 0
   
   
n=int(input())
g=[]
for i in range(0,n):
    s= [int(x) for x in input().split()]
    #p0=Point(s[0],s[1])
    g.append((s[0],s[1]))

q=int(input())
for i in range(0,q):
    s= [int(x) for x in input().split()]
    #pa=Point(s[0],s[1])
    rt=point_in_poly(s[0],s[1],g)
    print(rt)

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())
vs=[complex(*map(int,input().split())) for i in range(n)]
edges=[(p0,p1) for p0,p1 in zip(vs,vs[1:]+[vs[0]])]

q=int(input())

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

Submission status: Accepted

Solution code:
def dot(a: complex, b: complex):
    return (a.conjugate() * b).real


def cross(a: complex, b: complex):
    return (a.conjugate() * b).imag


def is_contained(p: complex, g: list):
    flag = False

    for i in range(len(g)):
        a, b = g[i] - p, g[(i + 1) % len(g)] - p
        if a.imag > b.imag:
            a, b = b, a
        if a.imag <= 0 and 0 < b.imag:
            if cross(a, b) < 0:
                flag = not(flag)
        if cross(a, b) == 0 and dot(a, b) <= 0:
            return 1

    return 2 if flag else 0


n = int(input())
g = [complex(*map(int, input().split())) for _ in range(n)]
q = int(input())

for _ in range(q):
    p = complex(*map(int, input().split()))
    print(is_contained(p, g))

Submission status: Accepted

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 or p == a or p == b:
            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: Accepted

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[j] + 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: 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, p1 - p0) 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, edge 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:
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:
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 and x0*x1+y0*y1 <= 0:
            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: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4
0 0
3 1
2 3
0 3
3
2 1
0 2
3 2

output:
2
1
0
"""

import sys

EPS = 1e-9


def generate_polygon(_e_info):
    for edge in _e_info:
        ex, ey = map(int, edge)
        init_polygon.append(ex + ey * 1j)

    return init_polygon


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 check_contains(g, p):
    flag = False
    for j in range(edges):
        a, b = g[j] - p, g[(j + 1) % edges] - p
        if abs(cross(a, b)) < EPS and dot(a, b) < EPS:
            return 1
        elif a.imag > b.imag:
            a, b = b, a

        if a.imag < EPS < b.imag and cross(a, b) > EPS:
            flag = not flag
    return 2 if flag else 0


def solve(_p_info):
    for point in _p_info:
        px, py = map(int, point)
        p = px + py * 1j
        print(check_contains(polygon, p))
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    edges = int(_input[0])
    e_info = map(lambda x: x.split(), _input[1:edges + 1])
    points = int(_input[edges + 1])
    p_info = map(lambda x: x.split(), _input[edges + 2:])

    init_polygon = list()
    polygon = generate_polygon(e_info)
    solve(p_info)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4
0 0
3 1
2 3
0 3
3
2 1
0 2
3 2

output:
2
1
0
"""

import sys

EPS = 1e-9


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 check_contains(g, p):
    flag = False
    for j in range(edges):
        a, b = g[j] - p, g[(j + 1) % edges] - p
        if abs(cross(a, b)) < EPS and dot(a, b) < EPS:
            return 1
        elif a.imag > b.imag:
            a, b = b, a

        if a.imag < EPS < b.imag and cross(a, b) > EPS:
            flag = not flag
    return 2 if flag else 0


def solve(_p_info):
    for point in _p_info:
        px, py = map(float, point)
        p = px + py * 1j
        print(check_contains(polygon, p))
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    edges = int(_input[0])
    e_info = map(lambda x: x.split(), _input[1:edges + 1])
    points = int(_input[edges + 1])
    p_info = map(lambda x: x.split(), _input[edges + 2:])

    polygon = [float(x) + float(y) * 1j for x, y in e_info]
    solve(p_info)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4
0 0
3 1
2 3
0 3
3
2 1
0 2
3 2

output:
2
1
0
"""

import sys

EPS = 1e-9


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 check_contains(g, p):
    flag = False
    for j in range(edges):
        a, b = g[j] - p, g[(j + 1) % edges] - p
        if abs(cross(a, b)) < EPS and dot(a, b) < EPS:
            return 1
        elif a.imag > b.imag:
            a, b = b, a

        if a.imag < EPS < b.imag and cross(a, b) > EPS:
            flag = not flag
    return 2 if flag else 0


def solve(_p_info):
    for point in _p_info:
        px, py = map(int, point)
        p = px + py * 1j
        print(check_contains(polygon, p))
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    edges = int(_input[0])
    e_info = map(lambda x: x.split(), _input[1:edges + 1])
    points = int(_input[edges + 1])
    p_info = map(lambda x: x.split(), _input[edges + 2:])

    polygon = [int(x) + int(y) * 1j for x, y in e_info]
    solve(p_info)

Submission status: Accepted

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):
    up = False
    down = False
    start_point = polygon[0]
    for p in polygon[::-1]:
        if start_point.imag > p.imag:
            up = True
            break
        elif start_point.imag < p.imag:
            down = True
            break
    flag = 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])

q = int(file_input.readline())

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

Submission status: Accepted

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
    for v1, v2 in zip(polygon[0:], polygon[1:]):
        a = v1 - point
        b = v2 - point
        if a.imag > b.imag:
            a, b = b, a
        cross_ab = cross(a, b)
        if a.imag <= 0 and b.imag > 0 and cross_ab > 0:
            flag = not flag
        if cross_ab == 0 and dot(a, b) <= 0:
            return 1
    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])

q = int(file_input.readline())

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

Submission status: Accepted

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
    for v1, v2 in zip(polygon[0:], polygon[1:]):
        a = v1 - point
        b = v2 - point
        if a.imag > b.imag:
            a, b = b, a
        cross_ab = cross(a, b)
        if cross_ab == 0 and dot(a, b) <= 0:
            return 1
        if a.imag <= 0 and b.imag > 0 and cross_ab > 0:
            flag = not flag
    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])

q = int(file_input.readline())

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

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 = [0] * n
for i in range(n):
    x, y = map(int, readline().split())
    pg[i] = complex(x, y)
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 = [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)))