本题没有可用的提交语言。

题目描述

给定是一个简单但不一定凸的多边形。给定也是飞机上的一条线。如果多边形沿着这条线切割,那么我们可能会得到几个较小的多边形。你的任务是找到切割的长度,即线和多边形交汇处段的总长度。

输入

输入包括一些案例。每个表壳的数据都出现在多个输入行上,其中第一个包含两个非负整数$n$和$m$,给出多边形的顶点数和要考虑的切割线数,$3 <= n <= 1000$。以下 n 行包含多边形顶点的坐标;每行包含顶点的$x$和 $y$ 坐标。顶点按顺时针或逆时针顺序给出。以下每 $m$个输入线包含四个数字;这些数字是定义切割线的两点的 $x$ 和 $y$坐标。如果多边形的顶点靠近切割线的$1e-8$,那么我们认为顶点位于切割线上。

输入由$n$和$m$等于0的行终止。

输出

对于每条切割线,打印线交汇处的段总长度和为该测试用例定义的多边形,小数点后有3位数字。注意:多边形的子称属于多边形。

上图说明了样品中多边形的第一条切割线。 输入数 1

9 5
0 0
0 2
1 1
2 2
3 1
4 2
5 1
6 2
6 0
-1 2 7.5 1
0 1 6 1
0 1.5 6 1.5
0 2 6 1
0 0 0 2
0 0

输出数位 1

2.798
6.000
3.000
2.954
2.000

来源

滑铁卢当地2005.06.11