Cut Length

题意翻译

给定n个点的任意多边形 给定m条直线求直线在多边形内部距离 在边上也算如在内

题目描述

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.

输入输出格式

输入格式

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 $ 10^{5} $ by absolute values.

输出格式

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} $ .

输入输出样例

输入样例 #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