给定简单(无自交)n 边形。不一定是凸的。还给你 m 行。对于每条线,求该线和 n 边形的公共部分的长度。
n 边形的边界属于多边形。 n 边形可能包含 180 度角。
输入
第一行包含整数 n 和 m (3 ≤ n ≤ 1000;1 ≤ m ≤ 100)。接下来的 n 行包含多边形顶点的坐标(顺时针或逆时针方向)。所有顶点都是不同的。
以下 m 行包含行描述。它们中的每一个都包含一条直线上两个不同的点(按其坐标)。
输入坐标中给出的全部为实数,小数点后最多给出两位数。它们的绝对值不超过 105。
输出
打印 m 行,第 i 行应包含给定 n 边形和第 i 行的公共部分的长度。如果绝对误差或相对误差不超过 10 - 6,则答案将被视为正确。
示例
输入 #1
4 3 0 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 -1
输出 #1
1.41421356237309514547 1.00000000000000000000 0.00000000000000000000