598F орчуулах · Codeforces.mn

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

-- [орчуулагдаж байгаа]

Жишээ тэстүүд

Оролт

Гаралт

1.41421356237309514547
1.00000000000000000000
0.00000000000000000000