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 105 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<br />0 0<br />1 0<br />1 1<br />0 1<br />0 0 1 1<br />0 0 0 1<br />0 0 1 -1<br />
输出
1.41421356237309514547<br />1.00000000000000000000<br />0.00000000000000000000<br />
加载中...