Given simple (without self-intersections) n-gon. It is not necessary convex. Also you are given m lines. For each line find the length of common part of the line and the n-gon.

The boundary of n-gon belongs to polygon. It is possible that n-gon contains 180-degree angles.


-----Input-----

The first line contains integers n and m (3 ≤ n ≤ 1000;1 ≤ m ≤ 100). The following n lines contain coordinates of polygon vertices (in clockwise or counterclockwise direction). All vertices are distinct.

The following m lines contain line descriptions. Each of them contains two distict points of a line by their coordinates.

All given in the input coordinates are real numbers, given with at most two digits after decimal point. They do not exceed 10^5 by absolute values.


-----Output-----

Print m lines, the i-th line should contain the length of common part of the given n-gon and the i-th line. The answer will be considered correct if the absolute or relative error doesn't exceed 10^{ - 6}.


-----Examples-----
Input
4 3
0 0
1 0
1 1
0 1
0 0 1 1
0 0 0 1
0 0 1 -1

Output
1.41421356237309514547
1.00000000000000000000
0.00000000000000000000

Difficulty: interview

Starter code:

Solutions:
def main():
    from math import hypot
    n, m = list(map(int, input().split()))
    vertices = list(tuple(map(float, input().split())) for _ in range(n))
    ax, ay = vertices[-1]
    for i, (bx, by) in enumerate(vertices):
        vertices[i], ax, ay = (bx, by, bx - ax, by - ay), bx, by
    for _ in range(m):
        x0, y0, x1, y1 = list(map(float, input().split()))
        x1 -= x0
        y1 -= y0
        bx, by = vertices[-1][:2]
        tmp = (bx - x0) * y1 - (by - y0) * x1
        t = -1 if tmp < 0 else 1 if tmp > 0 else 0
        res = []
        for bx, by, abx, aby in vertices:
            s, tmp = t, (bx - x0) * y1 - (by - y0) * x1
            t = -1 if tmp < 0 else 1 if tmp > 0 else 0
            if s != t:
                res.append((((bx - x0) * aby - (by - y0) * abx) / (x1 * aby - y1 * abx), s - t))
        res.sort()
        t, w = 0, 0.
        for i, (tmp, s) in enumerate(res, -1):
            if t:
                w += tmp - res[i][0]
            t += s
        print(w * hypot(x1, y1))


def __starting_point():
    main()

__starting_point()

def main():
    from math import hypot
    n, m = list(map(int, input().split()))
    vertices = list(tuple(map(float, input().split())) for _ in range(n))
    ax, ay = vertices[-1]
    for i, (bx, by) in enumerate(vertices):
        vertices[i], ax, ay = (bx, by, bx - ax, by - ay), bx, by
    for _ in range(m):
        x0, y0, x1, y1 = list(map(float, input().split()))
        x1 -= x0
        y1 -= y0
        bx, by = vertices[-1][:2]
        tmp = (bx - x0) * y1 - (by - y0) * x1
        t = -1 if tmp < 0 else 1 if tmp > 0 else 0
        res = []
        for bx, by, abx, aby in vertices:
            s, tmp = t, (bx - x0) * y1 - (by - y0) * x1
            t = -1 if tmp < 0 else 1 if tmp > 0 else 0
            if s != t:
                res.append((((bx - x0) * aby - (by - y0) * abx) / (x1 * aby - y1 * abx), s - t))
        res.sort()
        t, w = 0, 0.
        for i, (tmp, s) in enumerate(res, -1):
            if t:
                w += tmp - res[i][0]
            t += s
        print(w * hypot(x1, y1))


def __starting_point():
    main()


__starting_point()

def main():
    from math import hypot
    n, m = list(map(int, input().split()))
    vertices = list(tuple(map(float, input().split())) for _ in range(n))
    ax, ay = vertices[-1]
    for i, (bx, by) in enumerate(vertices):
        vertices[i], ax, ay = (bx, by, bx - ax, by - ay), bx, by
    for _ in range(m):
        x0, y0, x1, y1 = list(map(float, input().split()))
        x1 -= x0
        y1 -= y0
        bx, by = vertices[-1][:2]
        tmp = (bx - x0) * y1 - (by - y0) * x1
        t = -1 if tmp < 0 else 1 if tmp > 0 else 0
        res = []
        for bx, by, abx, aby in vertices:
            s, tmp = t, (bx - x0) * y1 - (by - y0) * x1
            t = -1 if tmp < 0 else 1 if tmp > 0 else 0
            if s != t:
                res.append((((bx - x0) * aby - (by - y0) * abx) / (x1 * aby - y1 * abx), s - t))
        res.sort()
        t, w = 0, 0.
        for i, (tmp, s) in enumerate(res, -1):
            if t:
                w += tmp - res[i][0]
            t += s
        print(w * hypot(x1, y1))


def __starting_point():
    main()


__starting_point()

def main():
    from math import hypot
    n, m = list(map(int, input().split()))
    vertices = list(tuple(map(float, input().split())) for _ in range(n))
    ax, ay = vertices[-1]
    for i, (bx, by) in enumerate(vertices):
        vertices[i], ax, ay = (bx, by, bx - ax, by - ay), bx, by
    for _ in range(m):
        x0, y0, x1, y1 = list(map(float, input().split()))
        x1 -= x0
        y1 -= y0
        bx, by = vertices[-1][:2]
        tmp = (bx - x0) * y1 - (by - y0) * x1
        t = -1 if tmp < 0 else 1 if tmp > 0 else 0
        res = []
        for bx, by, abx, aby in vertices:
            s, tmp = t, (bx - x0) * y1 - (by - y0) * x1
            t = -1 if tmp < 0 else 1 if tmp > 0 else 0
            if s != t:
                res.append((((bx - x0) * aby - (by - y0) * abx) / (x1 * aby - y1 * abx), s - t))
        res.sort()
        t, w = 0, 0.
        for i, (tmp, s) in enumerate(res, -1):
            if t:
                w += tmp - res[i][0]
            t += s
        print(w * hypot(x1, y1))


def __starting_point():
    main()


__starting_point()

def main():
    from math import hypot
    n, m = list(map(int, input().split()))
    vertices = list(tuple(map(float, input().split())) for _ in range(n))
    ax, ay = vertices[-1]
    for i, (bx, by) in enumerate(vertices):
        vertices[i], ax, ay = (bx, by, bx - ax, by - ay), bx, by
    for _ in range(m):
        x0, y0, x1, y1 = list(map(float, input().split()))
        x1 -= x0
        y1 -= y0
        bx, by = vertices[-1][:2]
        tmp = (bx - x0) * y1 - (by - y0) * x1
        t = -1 if tmp < 0 else 1 if tmp > 0 else 0
        res = []
        for bx, by, abx, aby in vertices:
            s, tmp = t, (bx - x0) * y1 - (by - y0) * x1
            t = -1 if tmp < 0 else 1 if tmp > 0 else 0
            if s != t:
                res.append((((bx - x0) * aby - (by - y0) * abx) / (x1 * aby - y1 * abx), s - t))
        res.sort()
        t, w = 0, 0.
        for i, (tmp, s) in enumerate(res, -1):
            if t:
                w += tmp - res[i][0]
            t += s
        print(w * hypot(x1, y1))


def __starting_point():
    main()


__starting_point()

def main():
    from math import hypot
    n, m = list(map(int, input().split()))
    vertices = list(tuple(map(float, input().split())) for _ in range(n))
    ax, ay = vertices[-1]
    for i, (bx, by) in enumerate(vertices):
        vertices[i], ax, ay = (bx, by, bx - ax, by - ay), bx, by
    for _ in range(m):
        x0, y0, x1, y1 = list(map(float, input().split()))
        x1 -= x0
        y1 -= y0
        bx, by = vertices[-1][:2]
        tmp = (bx - x0) * y1 - (by - y0) * x1
        t = -1 if tmp < 0 else 1 if tmp > 0 else 0
        res = []
        for bx, by, abx, aby in vertices:
            s, tmp = t, (bx - x0) * y1 - (by - y0) * x1
            t = -1 if tmp < 0 else 1 if tmp > 0 else 0
            if s != t:
                res.append((((bx - x0) * aby - (by - y0) * abx) / (x1 * aby - y1 * abx), s - t))
        res.sort()
        t, w = 0, 0.
        for i, (tmp, s) in enumerate(res, -1):
            if t:
                w += tmp - res[i][0]
            t += s
        print(w * hypot(x1, y1))


def __starting_point():
    main()


__starting_point()

def main():
    from math import hypot
    n, m = list(map(int, input().split()))
    vertices = list(tuple(map(float, input().split())) for _ in range(n))
    ax, ay = vertices[-1]
    for i, (bx, by) in enumerate(vertices):
        vertices[i], ax, ay = (bx, by, bx - ax, by - ay), bx, by
    for _ in range(m):
        x0, y0, x1, y1 = list(map(float, input().split()))
        x1 -= x0
        y1 -= y0
        bx, by = vertices[-1][:2]
        tmp = (bx - x0) * y1 - (by - y0) * x1
        t = -1 if tmp < 0 else 1 if tmp > 0 else 0
        res = []
        for bx, by, abx, aby in vertices:
            s, tmp = t, (bx - x0) * y1 - (by - y0) * x1
            t = -1 if tmp < 0 else 1 if tmp > 0 else 0
            if s != t:
                res.append((((bx - x0) * aby - (by - y0) * abx) / (x1 * aby - y1 * abx), s - t))
        res.sort()
        t, w = 0, 0.
        for i, (tmp, s) in enumerate(res, -1):
            if t:
                w += tmp - res[i][0]
            t += s
        print(w * hypot(x1, y1))


def __starting_point():
    main()


__starting_point()

def main():
    from math import hypot
    n, m = list(map(int, input().split()))
    vertices = list(tuple(map(float, input().split())) for _ in range(n))
    ax, ay = vertices[-1]
    for i, (bx, by) in enumerate(vertices):
        vertices[i], ax, ay = (bx, by, bx - ax, by - ay), bx, by
    for _ in range(m):
        x0, y0, x1, y1 = list(map(float, input().split()))
        x1 -= x0
        y1 -= y0
        bx, by = vertices[-1][:2]
        tmp = (bx - x0) * y1 - (by - y0) * x1
        t = -1 if tmp < 0 else 1 if tmp > 0 else 0
        res = []
        for bx, by, abx, aby in vertices:
            s, tmp = t, (bx - x0) * y1 - (by - y0) * x1
            t = -1 if tmp < 0 else 1 if tmp > 0 else 0
            if s != t:
                res.append((((bx - x0) * aby - (by - y0) * abx) / (x1 * aby - y1 * abx), s - t))
        res.sort()
        t, w = 0, 0.
        for i, (tmp, s) in enumerate(res, -1):
            if t:
                w += tmp - res[i][0]
            t += s
        print(w * hypot(x1, y1))


def __starting_point():
    main()


__starting_point()

import math

eps = 1e-9

def sign(n):
    if n > eps: return 1
    if n < -eps: return -1
    return 0

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

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

    def __add__(self, v):
        return Vector(self.x + v.x, self.y + v.y)
    
    def __sub__(self, v):
        return Vector(self.x - v.x, self.y - v.y)
    
    def length(self):
        return math.hypot(self.x, self.y)

def solve(polygon, p, q):
    intersections = []
    for (a, b) in zip(polygon, polygon[1:] + polygon[:1]):
        ss = sign(cross(a - p, q - p))
        es = sign(cross(b - p, q - p))

        if ss == es: continue

        t = cross(a - p, a - b) / cross(q - p, a - b)
        intersections.append((t, es - ss))
    intersections = sorted(intersections)
    total_t, previous_t, count = [0] * 3
    
    for t, order in intersections:
        if (count > 0): total_t += t - previous_t
        previous_t = t
        count += order
    # print(total_t) 

    print(total_t * (q - p).length())
    
n, m = list(map(int, input().split()))

polygon = []
for i in range(n):
    x, y = list(map(float, input().split()))
    polygon.append(Vector(x, y))
area = sum([cross(x[0], x[1]) for x in zip(polygon, polygon[1:] + polygon[:1])])
if (area < 0): polygon.reverse()

for i in range(m):
    x1, y1, x2, y2 = list(map(float, input().split()))
    solve(polygon, Vector(x1, y1), Vector(x2, y2))


def main():
    from math import hypot
    n, m = map(int, input().split())
    vertices = list(tuple(map(float, input().split())) for _ in range(n))
    ax, ay = vertices[-1]
    for i, (bx, by) in enumerate(vertices):
        vertices[i], ax, ay = (bx, by, bx - ax, by - ay), bx, by
    for _ in range(m):
        x0, y0, x1, y1 = map(float, input().split())
        x1 -= x0
        y1 -= y0
        bx, by = vertices[-1][:2]
        tmp = (bx - x0) * y1 - (by - y0) * x1
        t = -1 if tmp < 0 else 1 if tmp > 0 else 0
        res = []
        for bx, by, abx, aby in vertices:
            s, tmp = t, (bx - x0) * y1 - (by - y0) * x1
            t = -1 if tmp < 0 else 1 if tmp > 0 else 0
            if s != t:
                res.append((((bx - x0) * aby - (by - y0) * abx) / (x1 * aby - y1 * abx), s - t))
        res.sort()
        t, w = 0, 0.
        for i, (tmp, s) in enumerate(res, -1):
            if t:
                w += tmp - res[i][0]
            t += s
        print(w * hypot(x1, y1))
 
 
def __starting_point():
    main()
__starting_point()

import math
 
eps = 1e-9
 
def sign(n):
    if n > eps: return 1
    if n < -eps: return -1
    return 0
 
def cross(a, b):
    return a.x * b.y - a.y * b.x
 
class Vector:
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
    def __add__(self, v):
        return Vector(self.x + v.x, self.y + v.y)
    
    def __sub__(self, v):
        return Vector(self.x - v.x, self.y - v.y)
    
    def length(self):
        return math.hypot(self.x, self.y)
 
def solve(polygon, p, q):
    intersections = []
    for (a, b) in zip(polygon, polygon[1:] + polygon[:1]):
        ss = sign(cross(a - p, q - p))
        es = sign(cross(b - p, q - p))
 
        if ss == es: continue
 
        t = cross(a - p, a - b) / cross(q - p, a - b)
        intersections.append((t, es - ss))
    intersections = sorted(intersections)
    total_t, previous_t, count = [0] * 3
    
    for t, order in intersections:
        if (count > 0): total_t += t - previous_t
        previous_t = t
        count += order
    # print(total_t) 
 
    print(total_t * (q - p).length())
    
n, m = map(int, input().split())
 
polygon = []
for i in range(n):
    x, y = map(float, input().split())
    polygon.append(Vector(x, y))
area = sum(map(lambda x: cross(x[0], x[1]), zip(polygon, polygon[1:] + polygon[:1])))
if (area < 0): polygon.reverse()
 
for i in range(m):
    x1, y1, x2, y2 = map(float, input().split())
    solve(polygon, Vector(x1, y1), Vector(x2, y2))