<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

412. Expedition
Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

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?
Input
There are two integers at the first line of input — N and M (3 ≤ N ≤ 100000, 0 ≤ M ≤ 100000) — number of vertices in polygon, which tent is represented by, and the number of shelves. Following N lines contain 2 integers each (xi, yi) — 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
Output answer for the problem with at least 6 digits after decimal point.
Example(s)
sample input
sample output
3 1
0 2
-2 -1
3 -3
-1 -1 1 -1
4.615855548972
Explanatory picture:


sample input
sample output
4 3
-2 -2
2 -2
2 2
-2 2
-1 0 0 -1
1 -1 1 1
-1 1 1 1
12.000000
Explanatory picture:

<|response|>
## 1. Abridged problem statement

A convex polygon with `N` vertices represents the tent boundary. The lamp is at the origin `(0, 0)`, strictly inside the polygon.

There are `M` shelves, each represented by a segment strictly inside the polygon. A shelf blocks light along every ray from the origin that intersects the shelf. The blocked rays shade corresponding parts of the polygon boundary.

Compute the total length of shaded parts of the polygon boundary.

Constraints:

```text
3 ≤ N ≤ 100000
0 ≤ M ≤ 100000
```

The polygon is convex, vertices are given counter-clockwise, all shelves are inside the polygon, and no shelf contains the origin.

---

## 2. Key observations needed to solve the problem

### Observation 1: Boundary points correspond to directions

Because the polygon is convex and the origin is strictly inside it, every ray starting from the origin intersects the polygon boundary in exactly one point.

So there is a one-to-one correspondence:

```text
angle θ  <->  point on polygon boundary hit by ray θ
```

Thus, instead of directly working with boundary segments, we can work with angular intervals.

---

### Observation 2: Each shelf blocks one angular interval

A shelf is a segment `AB`.

From the origin, this segment subtends an angular interval between the directions of points `A` and `B`.

Let:

```cpp
angle(A) = atan2(A.y, A.x)
angle(B) = atan2(B.y, B.x)
```

The segment does not contain the origin, so the blocked angular interval is always the smaller arc between the two endpoint directions.

The cross product determines its direction:

```cpp
cross(A, B) = A.x * B.y - A.y * B.x
```

- If `cross(A, B) > 0`, the blocked interval is from `angle(A)` to `angle(B)` counter-clockwise.
- If `cross(A, B) < 0`, the blocked interval is from `angle(B)` to `angle(A)` counter-clockwise.
- If `cross(A, B) == 0`, the segment has zero angular width and contributes nothing.

Intervals crossing angle `0` are split into two intervals.

---

### Observation 3: Merge all blocked angular intervals

After converting all shelves into angular intervals, the shaded directions are simply the union of those intervals.

Sort the intervals and merge overlapping ones.

---

### Observation 4: Convert an angular interval to polygon boundary length

For a blocked angular interval `[l, r]`, we need the length of the polygon boundary swept by rays with angles from `l` to `r`.

Because the polygon is convex and contains the origin, sorting polygon vertices by polar angle gives the same cyclic order as walking along the boundary.

We can precompute:

```text
bound[i] = polar angle of vertex i
pref[i]  = boundary length from vertex 0 to vertex i
```

For any angle `θ`, binary search which polygon edge is hit by the ray. Then intersect the ray with that edge and compute the distance along the boundary from the starting vertex.

Define:

```text
S(θ) = boundary distance from chosen starting vertex to boundary point hit by ray θ
```

Then:

```text
length of boundary for interval [l, r] = S(r) - S(l)
```

with special handling for cyclic wraparound.

---

## 3. Full solution approach

### Step 1: Read input

Read the convex polygon and shelf segments.

---

### Step 2: Sort polygon vertices by angle

For every polygon vertex `P`, compute:

```cpp
atan2(P.y, P.x)
```

Normalize the angle to `[0, 2π)`.

Sort vertices by angle.

Since the polygon is convex and the origin is inside it, this sorted order is exactly a cyclic boundary order.

---

### Step 3: Precompute prefix boundary lengths

For sorted polygon vertices `poly[0], poly[1], ..., poly[n - 1]`, compute:

```cpp
pref[0] = 0
pref[i] = pref[i - 1] + distance(poly[i - 1], poly[i])
```

Also compute the full perimeter:

```cpp
perimeter = pref[n - 1] + distance(poly[n - 1], poly[0])
```

---

### Step 4: Define a function `arcLength(theta)`

This function returns the boundary distance from `poly[0]` to the point where the ray with direction `theta` hits the polygon.

To compute it:

1. Binary search the polygon edge whose angular range contains `theta`.
2. Intersect the ray from the origin with that edge.
3. Return prefix distance to the edge start plus distance along the edge to the intersection point.

---

### Step 5: Convert shelves to angular intervals

For each shelf segment `AB`:

1. Compute endpoint angles.
2. Use cross product to determine the correct counter-clockwise interval.
3. If the interval crosses `0`, split it.

Collect all intervals.

---

### Step 6: Merge intervals

Sort all angular intervals by start angle.

Then merge overlapping or touching intervals.

---

### Step 7: Convert merged intervals to boundary length

For each merged interval `[l, r]`, compute its shaded boundary length using `arcLength`.

Because `arcLength` is parameterized starting from the smallest polygon vertex angle `g0`, there are three cases:

1. Entire interval is before `g0`: shift by `2π`.
2. Entire interval is after `g0`: use directly.
3. Interval contains `g0`: split around the cyclic boundary start.

Accumulate all contributions.

---

### Complexity

Sorting polygon vertices:

```text
O(N log N)
```

Sorting shelf intervals:

```text
O(M log M)
```

Each merged interval uses binary search:

```text
O(log N)
```

Overall complexity:

```text
O((N + M) log(N + M))
```

Memory usage:

```text
O(N + M)
```

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

using ld = double;

const ld PI = acos(-1.0);
const ld TWO_PI = 2.0 * PI;
const ld EPS = 1e-10;

struct Point {
    ld x, y;

    Point(ld x = 0, ld y = 0) : x(x), y(y) {}

    Point operator + (const Point& other) const {
        return Point(x + other.x, y + other.y);
    }

    Point operator - (const Point& other) const {
        return Point(x - other.x, y - other.y);
    }

    Point operator * (ld k) const {
        return Point(x * k, y * k);
    }
};

ld cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

ld dist(Point a, Point b) {
    return hypot(a.x - b.x, a.y - b.y);
}

ld angleOf(Point p) {
    ld a = atan2(p.y, p.x);
    if (a < 0) a += TWO_PI;
    return a;
}

/*
    Intersects two infinite lines:
    line through a1 -> b1
    line through a2 -> b2

    In this problem, the first line is the ray direction line from origin,
    and the second line is the polygon edge line.
*/
Point lineIntersection(Point a1, Point b1, Point a2, Point b2) {
    Point d1 = b1 - a1;
    Point d2 = b2 - a2;

    ld t = cross(a2 - a1, d2) / cross(d1, d2);

    return a1 + d1 * t;
}

/*
    Fast input is useful because the limits are large and the time limit is tight.
*/
struct FastScanner {
    static const int BUFSIZE = 1 << 16;

    char buffer[BUFSIZE];
    int pos = 0, len = 0;

    char getChar() {
        if (pos == len) {
            len = fread(buffer, 1, BUFSIZE, stdin);
            pos = 0;
            if (len == 0) return EOF;
        }
        return buffer[pos++];
    }

    long long readInt() {
        char c = getChar();

        while (c != '-' && (c < '0' || c > '9')) {
            c = getChar();
        }

        bool neg = false;

        if (c == '-') {
            neg = true;
            c = getChar();
        }

        long long value = 0;

        while (c >= '0' && c <= '9') {
            value = value * 10 + (c - '0');
            c = getChar();
        }

        return neg ? -value : value;
    }
};

int main() {
    FastScanner fs;

    int n = fs.readInt();
    int m = fs.readInt();

    vector<Point> polygon(n);

    for (int i = 0; i < n; i++) {
        polygon[i].x = fs.readInt();
        polygon[i].y = fs.readInt();
    }

    vector<pair<Point, Point>> shelves(m);

    for (int i = 0; i < m; i++) {
        shelves[i].first.x = fs.readInt();
        shelves[i].first.y = fs.readInt();
        shelves[i].second.x = fs.readInt();
        shelves[i].second.y = fs.readInt();
    }

    /*
        Sort polygon vertices by polar angle around the origin.

        Since the polygon is convex and contains the origin, this sorted order
        is the same as the polygon boundary order, up to a cyclic shift.
    */
    vector<pair<ld, Point>> byAngle;

    for (Point p : polygon) {
        byAngle.push_back({angleOf(p), p});
    }

    sort(byAngle.begin(), byAngle.end());

    for (int i = 0; i < n; i++) {
        polygon[i] = byAngle[i].second;
    }

    /*
        bound[i] = polar angle of polygon[i]
        bound[n] = bound[0] + 2*pi, used for the closing edge
    */
    vector<ld> bound(n + 1);

    for (int i = 0; i < n; i++) {
        bound[i] = byAngle[i].first;
    }

    bound[n] = bound[0] + TWO_PI;

    /*
        Prefix lengths along the polygon boundary starting from polygon[0].
    */
    vector<ld> pref(n + 1, 0.0);

    for (int i = 1; i < n; i++) {
        pref[i] = pref[i - 1] + dist(polygon[i - 1], polygon[i]);
    }

    ld perimeter = pref[n - 1] + dist(polygon[n - 1], polygon[0]);

    ld startAngle = bound[0];

    /*
        Returns boundary distance from polygon[0] to the point where the ray
        of angle theta hits the polygon.

        theta must be in [startAngle, startAngle + 2*pi].
    */
    auto boundaryDistance = [&](ld theta) -> ld {
        int edge = int(upper_bound(bound.begin(), bound.end(), theta) - bound.begin()) - 1;

        if (edge >= n) edge = n - 1;

        Point dir(cos(theta), sin(theta));

        Point hit = lineIntersection(
            Point(0, 0),
            dir,
            polygon[edge],
            polygon[(edge + 1) % n]
        );

        return pref[edge] + dist(polygon[edge], hit);
    };

    /*
        Convert shelves to angular intervals.
    */
    vector<pair<ld, ld>> intervals;

    auto addInterval = [&](ld l, ld r) {
        if (l <= r) {
            intervals.push_back({l, r});
        } else {
            /*
                Interval crosses 0, so split it.
            */
            intervals.push_back({l, TWO_PI});
            intervals.push_back({0.0, r});
        }
    };

    for (auto shelf : shelves) {
        Point a = shelf.first;
        Point b = shelf.second;

        ld c = cross(a, b);

        /*
            If c == 0, both endpoints lie on the same ray from the origin.
            The shelf has zero angular width.
        */
        if (fabs(c) < EPS) {
            continue;
        }

        ld angleA = angleOf(a);
        ld angleB = angleOf(b);

        /*
            The sign of the cross product tells which endpoint comes first
            in the smaller counter-clockwise arc.
        */
        if (c > 0) {
            addInterval(angleA, angleB);
        } else {
            addInterval(angleB, angleA);
        }
    }

    /*
        Sort and merge blocked angular intervals.
    */
    sort(intervals.begin(), intervals.end());

    ld answer = 0.0;

    auto intervalBoundaryLength = [&](ld l, ld r) -> ld {
        /*
            The boundaryDistance function starts from startAngle.

            If an angular interval lies completely before startAngle,
            shift it by 2*pi.

            If it contains startAngle, split it across the cyclic boundary.
        */

        if (l < startAngle - EPS && r > startAngle + EPS) {
            return (perimeter - boundaryDistance(l + TWO_PI)) +
                   boundaryDistance(r);
        }

        if (r <= startAngle + EPS) {
            return boundaryDistance(r + TWO_PI) -
                   boundaryDistance(l + TWO_PI);
        }

        return boundaryDistance(r) - boundaryDistance(l);
    };

    ld curL = 0.0;
    ld curR = -1.0;

    for (auto interval : intervals) {
        ld l = interval.first;
        ld r = interval.second;

        if (curR < curL) {
            curL = l;
            curR = r;
        } else if (l <= curR + EPS) {
            curR = max(curR, r);
        } else {
            answer += intervalBoundaryLength(curL, curR);
            curL = l;
            curR = r;
        }
    }

    if (curR >= curL) {
        answer += intervalBoundaryLength(curL, curR);
    }

    cout.setf(ios::fixed);
    cout << setprecision(12) << answer << '\n';

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys
import math
import bisect


EPS = 1e-12
PI = math.pi
TWO_PI = 2.0 * math.pi


def norm_angle(a):
    """
    Normalize angle to [0, 2*pi).
    """
    if a < 0:
        a += TWO_PI
    return a


def cross(a, b):
    """
    Cross product of vectors a and b.
    Points are represented as tuples (x, y).
    """
    return a[0] * b[1] - a[1] * b[0]


def dist(a, b):
    """
    Euclidean distance between two points.
    """
    return math.hypot(a[0] - b[0], a[1] - b[1])


def line_ray_edge_intersection(theta, p, q):
    """
    Intersect the line from origin in direction theta
    with the line containing polygon edge p -> q.

    The chosen edge is correct, so the intersection lies on that edge.
    """
    dx = math.cos(theta)
    dy = math.sin(theta)

    ex = q[0] - p[0]
    ey = q[1] - p[1]

    # Solve:
    # t * direction = p + u * edge
    #
    # Taking cross product with edge:
    # t * cross(direction, edge) = cross(p, edge)
    denom = dx * ey - dy * ex
    numer = p[0] * ey - p[1] * ex

    t = numer / denom

    return (dx * t, dy * t)


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))

    idx = 0

    n = data[idx]
    m = data[idx + 1]
    idx += 2

    polygon = []

    for _ in range(n):
        x = data[idx]
        y = data[idx + 1]
        idx += 2
        polygon.append((float(x), float(y)))

    shelves = []

    for _ in range(m):
        x1 = data[idx]
        y1 = data[idx + 1]
        x2 = data[idx + 2]
        y2 = data[idx + 3]
        idx += 4

        shelves.append(((float(x1), float(y1)), (float(x2), float(y2))))

    """
    Sort polygon vertices by polar angle.

    For a convex polygon containing the origin, this order is the same as
    walking along the polygon boundary, up to cyclic shift.
    """
    by_angle = []

    for p in polygon:
        ang = norm_angle(math.atan2(p[1], p[0]))
        by_angle.append((ang, p))

    by_angle.sort()

    polygon = [p for _, p in by_angle]

    bound = [ang for ang, _ in by_angle]

    """
    Add artificial closing angle.
    """
    bound.append(bound[0] + TWO_PI)

    """
    Prefix boundary lengths from polygon[0].
    """
    pref = [0.0] * (n + 1)

    for i in range(1, n):
        pref[i] = pref[i - 1] + dist(polygon[i - 1], polygon[i])

    perimeter = pref[n - 1] + dist(polygon[n - 1], polygon[0])

    start_angle = bound[0]

    def boundary_distance(theta):
        """
        Return boundary distance from polygon[0] to the point where
        the ray with angle theta hits the polygon.

        theta must be in [start_angle, start_angle + 2*pi].
        """
        edge = bisect.bisect_right(bound, theta) - 1

        if edge >= n:
            edge = n - 1

        p = polygon[edge]
        q = polygon[(edge + 1) % n]

        hit = line_ray_edge_intersection(theta, p, q)

        return pref[edge] + dist(p, hit)

    """
    Convert each shelf into one angular interval.
    """
    intervals = []

    def add_interval(l, r):
        """
        Add counter-clockwise interval from l to r.
        If it crosses angle 0, split it.
        """
        if l <= r:
            intervals.append((l, r))
        else:
            intervals.append((l, TWO_PI))
            intervals.append((0.0, r))

    for a, b in shelves:
        c = cross(a, b)

        """
        If the cross product is zero, the shelf has zero angular width.
        """
        if abs(c) < EPS:
            continue

        angle_a = norm_angle(math.atan2(a[1], a[0]))
        angle_b = norm_angle(math.atan2(b[1], b[0]))

        """
        Choose the smaller counter-clockwise angular interval.
        """
        if c > 0:
            add_interval(angle_a, angle_b)
        else:
            add_interval(angle_b, angle_a)

    """
    Sort and merge angular intervals.
    """
    intervals.sort()

    def interval_boundary_length(l, r):
        """
        Convert angular interval [l, r] to boundary length.
        """
        if l < start_angle - EPS and r > start_angle + EPS:
            return (perimeter - boundary_distance(l + TWO_PI)) + \
                   boundary_distance(r)

        if r <= start_angle + EPS:
            return boundary_distance(r + TWO_PI) - \
                   boundary_distance(l + TWO_PI)

        return boundary_distance(r) - boundary_distance(l)

    answer = 0.0

    cur_l = 0.0
    cur_r = -1.0

    for l, r in intervals:
        if cur_r < cur_l:
            cur_l = l
            cur_r = r
        elif l <= cur_r + EPS:
            cur_r = max(cur_r, r)
        else:
            answer += interval_boundary_length(cur_l, cur_r)
            cur_l = l
            cur_r = r

    if cur_r >= cur_l:
        answer += interval_boundary_length(cur_l, cur_r)

    print(f"{answer:.12f}")


if __name__ == "__main__":
    solve()
```