F. Cut Length

хугацааны хязгаарлалт 0.5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

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

Орчуулсан: [орчуулагдаж байгаа]

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

4 3
0 0
1 0
1 1
0 1
0 0 1 1
0 0 0 1
0 0 1 -1
Сэтгэгдлүүдийг ачааллаж байна...