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: VERY_HARD
Tags: Geometry

Starter code:

Solutions:
import math
eps = 1e-09

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 * (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.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()