CF598F.Cut Length

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.

给定一个简单（无自交）的 $n$ 边形，它不一定是凸的。同时给定 $m$ 条直线。对每条直线，求该直线与 $n$ 边形的公共部分的长度。

$n$ 边形的边界属于该多边形。该 $n$ 边形可能含有 $180^\circ$ 的内角。

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 105 by absolute values.

第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 1000$；$1 \leq m \leq 100$）。接下来的 $n$ 行包含多边形顶点的坐标（按顺时针或逆时针顺序给出）。所有顶点互不相同。

接下来的 $m$ 行描述直线。每行通过其上两个不同点的坐标来描述一条直线。

输入中给出的所有坐标均为实数，小数点后最多保留两位数字，且其绝对值不超过 $10^5$。

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.

输出 m 行，其中第 i 行应包含给定的 n 边形与第 i 条直线的公共部分的长度。若答案的绝对误差或相对误差不超过 10 - 6，则视为正确。