Time limit per test: 0.75
Memory limit: 65536
Summer comes! Peter waited for it a lot. This is not surprising — Peter goes to his first geological expedition. And do you
know what is the main item at the expedition? Certainly, large tent. Peter noticed that when tent is put up, it
has the shape of convex polygon with N
vertices while observing from above.
But it is not enough to take only a tent. Peter will need other equipment. It was decided to place all the equipment at M
shelves inside the tent.
Each shelf is infinitely narrow, so it can be represented as a segment at the scheme of the tent.
Shelves are made differently, so corresponding segments can touch or intersect each other.
Also Peter puts a lamp to the center of the tent. At the scheme the lamp has (0,0) coordinates. Peter noticed, that shelves block the
light, so part of tent's walls becomes shaded. Peter has remembered, that he'd left his boots near some wall.
To decide, how difficult it would be to find them, Peter needs to know, what is the total length of walls' shaded parts?
Could you help him to find the answer for this question?
There are two integers at the first line of input — N
(3 ≤ N
≤ 100000, 0 ≤ M
≤ 100000) —
number of vertices in polygon, which tent is represented by, and the number of shelves.
lines contain 2 integers each (xi
) — coordinates of i
-th vertex of polygon.
Vertices are given in counter-clockwise order. Following M
lines contain 4 integers
—coordinates of the segment, which represents j
-th shelf. All coordinates in the input
do not exceed 106
by absolute value. It is guaranteed, that the point (0,0) and each segment lie strictly inside the polygon.
None of segments contains the point (0, 0).
Output answer for the problem with at least 6 digits after decimal point.
-1 -1 1 -1
-1 0 0 -1
1 -1 1 1
-1 1 1 1