Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
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
Гаралт
1.41421356237309514547 1.00000000000000000000 0.00000000000000000000