A10134 | Cut Length

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