← 返回题目列表

Codeforces · 598/F

F. 切割长度

中文机器翻译题面 查看原题

给定简单(无自交)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