Cutting a Polygon

A simple polygon (not necessarily convex) and a line in the plane are given. If the polygon is cut along the line, it may split into several smaller polygons. Find the length of the cut, that is, the total length of the segments that form the intersection of the line and the polygon.

The input consists of several test cases. Each test case begins with a line containing two non-negative integers $n$ and $m$ ($3 \le n \le 1000$): the number of vertices of the polygon and the number of cutting lines to consider. The next $n$ lines contain the $x$ and $y$ coordinates of the vertices, given in either clockwise or counterclockwise order. Each of the following $m$ lines contains four numbers $x_1\ y_1\ x_2\ y_2$, the coordinates of two distinct points that define a cutting line. If a vertex of the polygon is closer than 10e-8 to a cutting line, the vertex is considered to lie on the line. The input is terminated by a line with $n$ and $m$ both equal to $0$, which is not processed.

For each cutting line, print on its own line the total length of the segments in the intersection of the line and the polygon, rounded to exactly 3 digits after the decimal point. The perimeter of the polygon is considered to belong to the polygon.

Because the perimeter of the polygon belongs to the polygon, an edge that lies exactly along the cutting line contributes its full length to the intersection, whereas a line that meets the polygon at only a single vertex contributes a length of $0$.