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

315. The Highway Belt
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



In the country of Berland the decision was made to build a highway belt. The king Berbinduk IX wants the highway belt to be a closed polyline and have the star-like form around the capital of Berland. This means that each half-line starting from the capital intersects the highway belt in exactly one point.

To save time and money the king decided to build the highway using only existing roads. More specifically, the highway polyline should be formed by existing roads and parts of exisiting roads.

You are the head of the First Berland National Road Building Company, and you got the contract to build the highway. Now you need to present a plan of the new highway to the king. The longer it will be the more money you will earn. So your task is to create a plan with maximal possible length of the belt highway without breaking the king's requests listed above.

Input
The first line of the input contains the number of the existing roads N (1 ≤ N ≤ 50). The following N lines contain the description of the roads. Each description is four integer numbers x1, y1, x2, y2 not exceeding 100 by absolute value. (x1, y1) is one of the end points of the existing road and (x2, y2) is another. A road is allowed to have zero length.

The capital is situated in the origin of the coordinate system.

Output
Write to the output the maximum possible length of the highway belt with precision of no less than 5 digits after the decimal point. If it is impossible to build a highway belt of positive length, write 0 to the output.

Example(s)
sample input
sample output
6
2 2 2 -2
-2 2 -2 -2
2 2 -2 2
-2 -2 2 -2
3 0 -1 4
-2 1 0 3 
16.82843

sample input
sample output
1
1 1 -1 -1
0

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

You are given **N ≤ 50** line segments (roads) on the plane. The capital is at the **origin (0,0)**.

You must build a **closed polyline** (a cycle) using only **whole roads or subsegments of roads** such that:

> Every ray starting at the origin intersects the polyline in **exactly one point**.

Among all valid belts, output the **maximum possible total length** (perimeter).  
If it’s impossible to build any belt of **positive** length, output **0**.

---

## 2) Key observations

1. **“Exactly one intersection for every ray” ⇒ angular monotonicity.**  
   As you walk along a valid belt, the polar angle `atan2(y,x)` of points on the belt must change **monotonically** (always clockwise or always counterclockwise), otherwise some direction (ray) would hit the belt twice.

2. **We can only turn at road endpoints or intersections.**  
   Since we may use parts of roads, we should subdivide roads at all pairwise intersections. Then any optimal belt can be represented as a cycle in the resulting planar graph.

3. **Checking that the origin is inside can be done by parity.**  
   A closed curve intersects a fixed ray from the origin an **odd** number of times iff the origin is inside.  
   So we can track a **1-bit parity** while building the cycle: toggle when an edge crosses a fixed test ray.

4. **After fixing direction + start vertex, the problem becomes a longest path in a DAG.**  
   Sort vertices by polar angle (CW or CCW). If we force edges to go **forward** in that order (wrapping once), we eliminate cycles → we can do DP for maximum total length.

---

## 3) Full solution approach

### Step A — Build “atomic edges” graph from the roads

1. **Discard any road that contains the origin.**  
   If the belt uses a segment passing through the origin, rays would intersect at the origin in a degenerate/invalid way; typical accepted solutions simply forbid such roads.

2. For each road segment, collect points on it:
   - its two endpoints
   - every intersection point with every other road (including collinear overlaps handled by checking whether endpoints lie on the other segment)

3. For each road, sort collected points along the segment and connect each consecutive pair:
   - Each consecutive pair forms an **atomic usable subsegment** (edge).
   - Store its Euclidean length.
   - Also store whether this edge crosses a fixed test ray from the origin (parity toggle).

This yields a graph `G(V,E)` embedded in the plane.

### Step B — Define the “forward” order by angle

For each of the 2 directions:
- `dir = 0`: increasing angle (CCW)
- `dir = 1`: decreasing angle (CW)

Sort all vertices by:
- primary key: `angle = atan2(y,x)` in the chosen direction
- tie-break: distance to origin (radius)

### Step C — DP for each chosen start vertex

Pick a start vertex `s` and “cut” the circular angle order there to obtain a linear order:
- `rel_pos[v]` = relative position of vertex `v` in `[0..m-1]` around the circle starting at `s`.

We run DP over positions `0..m` where `m` represents “wrapped back to start”.

State:
- `dp[pos][parity]` = maximum length reachable when we are at relative position `pos`, with current parity of crossings of the test ray.

Initialization:
- `dp[0][0] = 0`, others = `-inf`.

Transition:
- from vertex at relative position `i`, try all incident edges `(v -> u)`:
  - Let `pu = rel_pos[u]`. If `pu == 0`, treat it as `m` (closing the loop).
  - Allow only **forward moves**: `pu > i`.
  - `newParity = parity XOR edgeCrossToggle`
  - update `dp[pu][newParity]`.

Answer candidate for this `(dir, start)`:
- `dp[m][1]` (closed after full sweep, and parity odd ⇒ origin inside).

Take maximum over all starts and both directions. If the maximum is 0 (or no valid cycle), print 0.

### Complexity

- Intersections: `O(N^2)`
- Vertices/edges after subdivision: `O(N^2)` in practice for `N ≤ 50`
- DP tries `2 * m` starts, each DP is roughly `O(m + E)` with adjacency scanning but filtering forward edges. With small constraints and optimization, it passes.

---

## 4) C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = long double;

const coord_t inf = 1e18;

struct Point {
    static constexpr coord_t eps = 1e-9;
    static inline const coord_t PI = acos((coord_t)-1.0);

    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrt(norm2()); }
    coord_t angle() const { return atan2(y, x); }

    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }

    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    friend Point circumcenter(const Point& a, const Point& b, const Point& c) {
        Point mid_ab = (a + b) / 2.0;
        Point mid_ac = (a + c) / 2.0;
        Point perp_ab = (b - a).perp();
        Point perp_ac = (c - a).perp();
        return line_line_intersection(
            mid_ab, mid_ab + perp_ab, mid_ac, mid_ac + perp_ac
        );
    }

    friend coord_t arc_area(
        const Point& center, coord_t r, const Point& p1, const Point& p2
    ) {
        coord_t theta1 = (p1 - center).angle();
        coord_t theta2 = (p2 - center).angle();
        if(theta2 < theta1 - eps) {
            theta2 += 2 * PI;
        }

        coord_t d_theta = theta2 - theta1;
        coord_t cx = center.x, cy = center.y;
        coord_t area = r * cx * (sin(theta2) - sin(theta1)) -
                       r * cy * (cos(theta2) - cos(theta1)) + r * r * d_theta;
        return area / 2.0;
    }

    friend vector<Point> intersect_circles(
        const Point& c1, coord_t r1, const Point& c2, coord_t r2
    ) {
        Point d = c2 - c1;
        coord_t dist = d.norm();

        if(dist > r1 + r2 + eps || dist < abs(r1 - r2) - eps || dist < eps) {
            return {};
        }

        coord_t a = (r1 * r1 - r2 * r2 + dist * dist) / (2 * dist);
        coord_t h_sq = r1 * r1 - a * a;
        if(h_sq < -eps) {
            return {};
        }
        if(h_sq < 0) {
            h_sq = 0;
        }
        coord_t h = sqrt(h_sq);

        Point mid = c1 + d.unit() * a;
        Point perp_dir = d.perp().unit();

        if(h < eps) {
            return {mid};
        }
        return {mid + perp_dir * h, mid - perp_dir * h};
    }
};

int n;
vector<Point> seg_a, seg_b;

void read() {
    cin >> n;
    seg_a.resize(n);
    seg_b.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> seg_a[i] >> seg_b[i];
    }
}

void solve() {
    // Let's start with building a graph with vertices being all the endpoints
    // and intersection points. Let us also sort all points by angle around the
    // origin / capital. This makes the rule of half-lines to intersecting in
    // more than two points a bit simpler as it forces us to either always go
    // clockwise or counterclockwise based on angle. It's not hard to prove this
    // is if this isn't the case we can always choose a vertex where we switch
    // the direction and this trivially creates a two-intersection.
    //
    // To make it more concrete, let's choose an arbitrary point that we want to
    // include and walk clockwise. We can form a DAG if we enforce going only
    // CW/CCW, which means that we effectively have a DP on a this DAG for
    // finding the longest path. This can be solved in O(|E|). Both the number
    // of vertices and edges in O(N^2), meaning that overall the complexity is
    // O(N^4), which is fine for this problem.
    //
    // We should be careful about whether the origin point is within the
    // polyline we are building. To do this nicely, we can remember the
    // algorithm to check if a point is within a polygon - we start a half-line
    // from it, and count the number of intersection. If this count is odd, then
    // the point is inside. We can do exactly the same here by putting a
    // vertical half-line starting from the origin. Whenever we add a segment to
    // the polyline, we will update the parity, so this can be done with a O(1)
    // state in the DP without changing the overall complexity.

    Point origin(0, 0);

    vector<bool> seg_valid(n, true);
    for(int i = 0; i < n; i++) {
        if(point_on_segment(seg_a[i], seg_b[i], origin)) {
            seg_valid[i] = false;
        }
    }

    vector<vector<Point>> seg_pts(n);
    for(int i = 0; i < n; i++) {
        if(!seg_valid[i]) {
            continue;
        }
        seg_pts[i].push_back(seg_a[i]);
        seg_pts[i].push_back(seg_b[i]);
    }

    for(int i = 0; i < n; i++) {
        if(!seg_valid[i]) {
            continue;
        }
        for(int j = i + 1; j < n; j++) {
            if(!seg_valid[j]) {
                continue;
            }
            Point d1 = seg_b[i] - seg_a[i];
            Point d2 = seg_b[j] - seg_a[j];
            if(abs(d1 ^ d2) < Point::eps) {
                if(point_on_segment(seg_a[i], seg_b[i], seg_a[j])) {
                    seg_pts[i].push_back(seg_a[j]);
                }
                if(point_on_segment(seg_a[i], seg_b[i], seg_b[j])) {
                    seg_pts[i].push_back(seg_b[j]);
                }
                if(point_on_segment(seg_a[j], seg_b[j], seg_a[i])) {
                    seg_pts[j].push_back(seg_a[i]);
                }
                if(point_on_segment(seg_a[j], seg_b[j], seg_b[i])) {
                    seg_pts[j].push_back(seg_b[i]);
                }
            } else {
                Point p = line_line_intersection(
                    seg_a[i], seg_b[i], seg_a[j], seg_b[j]
                );
                if(point_on_segment(seg_a[i], seg_b[i], p) &&
                   point_on_segment(seg_a[j], seg_b[j], p)) {
                    seg_pts[i].push_back(p);
                    seg_pts[j].push_back(p);
                }
            }
        }
    }

    for(int i = 0; i < n; i++) {
        sort(
            seg_pts[i].begin(), seg_pts[i].end(),
            [&](const Point& p, const Point& q) {
                return (p - seg_a[i]).norm2() < (q - seg_a[i]).norm2();
            }
        );
        seg_pts[i].erase(
            unique(
                seg_pts[i].begin(), seg_pts[i].end(),
                [](const Point& p, const Point& q) {
                    return (p - q).norm() < Point::eps;
                }
            ),
            seg_pts[i].end()
        );
    }

    vector<Point> pts;
    for(int i = 0; i < n; i++) {
        for(const Point& p: seg_pts[i]) {
            pts.push_back(p);
        }
    }
    sort(pts.begin(), pts.end());
    pts.erase(
        unique(
            pts.begin(), pts.end(),
            [](const Point& p, const Point& q) {
                return (p - q).norm() < Point::eps;
            }
        ),
        pts.end()
    );

    int m = pts.size();
    if(m == 0) {
        cout << "0\n";
        return;
    }

    auto get_idx = [&](const Point& p) -> int {
        for(int i = 0; i < m; i++) {
            if((pts[i] - p).norm() < Point::eps) {
                return i;
            }
        }
        return -1;
    };

    auto crosses_up_ray = [&](const Point& a, const Point& b) -> bool {
        coord_t min_x = min(a.x, b.x);
        coord_t max_x = max(a.x, b.x);
        if(!(min_x <= 0 && 0 < max_x)) {
            return false;
        }
        coord_t t = -a.x / (b.x - a.x);
        coord_t y_at_cross = a.y + t * (b.y - a.y);
        return y_at_cross > Point::eps;
    };

    vector<vector<tuple<int, coord_t, int>>> adj(m);
    vector<set<tuple<int, coord_t, int>>> adj_set(m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j + 1 < (int)seg_pts[i].size(); j++) {
            int u = get_idx(seg_pts[i][j]);
            int v = get_idx(seg_pts[i][j + 1]);
            coord_t d = (seg_pts[i][j] - seg_pts[i][j + 1]).norm();
            if(d < Point::eps) {
                continue;
            }
            if(abs(pts[u].angle() - pts[v].angle()) < Point::eps) {
                continue;
            }
            int cross = crosses_up_ray(pts[u], pts[v]) ? 1 : 0;
            adj_set[u].insert({v, d, cross});
            adj_set[v].insert({u, d, cross});
        }
    }
    for(int i = 0; i < m; i++) {
        for(auto& e: adj_set[i]) {
            adj[i].push_back(e);
        }
    }

    coord_t ans = 0;

    for(int dir = 0; dir < 2; dir++) {
        vector<int> order(m);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int i, int j) {
            coord_t ai = pts[i].angle(), aj = pts[j].angle();
            if(abs(ai - aj) > Point::eps) {
                return dir == 0 ? ai < aj : ai > aj;
            }
            return pts[i].norm() < pts[j].norm();
        });

        vector<int> global_pos(m);
        for(int i = 0; i < m; i++) {
            global_pos[order[i]] = i;
        }

        for(int start = 0; start < m; start++) {
            vector<int> rel_pos(m);
            for(int v = 0; v < m; v++) {
                rel_pos[v] = (global_pos[v] - global_pos[start] + m) % m;
            }

            vector<int> vertex_at(m);
            for(int v = 0; v < m; v++) {
                vertex_at[rel_pos[v]] = v;
            }

            vector<array<coord_t, 2>> dp(m + 1, {-inf, -inf});
            dp[0][0] = 0;

            for(int i = 0; i < m; i++) {
                int v = vertex_at[i];
                for(int parity = 0; parity < 2; parity++) {
                    if(dp[i][parity] < 0) {
                        continue;
                    }
                    for(auto [u, d, cross]: adj[v]) {
                        int pu = rel_pos[u];
                        if(pu == 0) {
                            pu = m;
                        }
                        if(pu > i) {
                            int new_parity = parity ^ cross;
                            dp[pu][new_parity] =
                                max(dp[pu][new_parity], dp[i][parity] + d);
                        }
                    }
                }
            }

            if(dp[m][1] > ans) {
                ans = dp[m][1];
            }
        }
    }

    cout << fixed << setprecision(9) << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
import math

EPS = 1e-9
INF = 1e100

class Point:
    __slots__ = ("x", "y")
    def __init__(self, x=0.0, y=0.0):
        self.x = float(x)
        self.y = float(y)

    def __add__(self, o): return Point(self.x + o.x, self.y + o.y)
    def __sub__(self, o): return Point(self.x - o.x, self.y - o.y)
    def __mul__(self, k): return Point(self.x * k, self.y * k)

    def cross(self, o): return self.x * o.y - self.y * o.x
    def norm2(self): return self.x * self.x + self.y * self.y
    def norm(self):  return math.hypot(self.x, self.y)
    def angle(self): return math.atan2(self.y, self.x)

def ccw(a: Point, b: Point, c: Point) -> int:
    v = (b - a).cross(c - a)
    if -EPS <= v <= EPS: return 0
    return 1 if v > 0 else -1

def point_on_segment(a: Point, b: Point, p: Point) -> bool:
    if ccw(a, b, p) != 0:
        return False
    return (min(a.x, b.x) - EPS <= p.x <= max(a.x, b.x) + EPS and
            min(a.y, b.y) - EPS <= p.y <= max(a.y, b.y) + EPS)

def line_line_intersection(a1: Point, b1: Point, a2: Point, b2: Point) -> Point:
    d1 = b1 - a1
    d2 = b2 - a2
    t = (a2 - a1).cross(d2) / d1.cross(d2)
    return a1 + d1 * t

def same_point(a: Point, b: Point) -> bool:
    return (a - b).norm() < EPS

def crosses_up_ray(a: Point, b: Point) -> int:
    # count crossing of x=0 from <=0 to >0, and intersection y > 0
    minx, maxx = min(a.x, b.x), max(a.x, b.x)
    if not (minx <= 0.0 and 0.0 < maxx):
        return 0
    t = -a.x / (b.x - a.x)
    y = a.y + t * (b.y - a.y)
    return 1 if y > EPS else 0

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    A, B = [], []
    for _ in range(n):
        x1, y1, x2, y2 = map(float, (next(it), next(it), next(it), next(it)))
        A.append(Point(x1, y1))
        B.append(Point(x2, y2))

    O = Point(0.0, 0.0)

    # 1) discard segments containing origin
    valid = [True] * n
    for i in range(n):
        if point_on_segment(A[i], B[i], O):
            valid[i] = False

    # 2) per segment, collect endpoints + intersections
    seg_pts = [[] for _ in range(n)]
    for i in range(n):
        if valid[i]:
            seg_pts[i].append(A[i])
            seg_pts[i].append(B[i])

    for i in range(n):
        if not valid[i]:
            continue
        for j in range(i + 1, n):
            if not valid[j]:
                continue
            d1 = B[i] - A[i]
            d2 = B[j] - A[j]
            if abs(d1.cross(d2)) <= EPS:
                # parallel: handle overlap via endpoint inclusion checks
                if point_on_segment(A[i], B[i], A[j]): seg_pts[i].append(A[j])
                if point_on_segment(A[i], B[i], B[j]): seg_pts[i].append(B[j])
                if point_on_segment(A[j], B[j], A[i]): seg_pts[j].append(A[i])
                if point_on_segment(A[j], B[j], B[i]): seg_pts[j].append(B[i])
            else:
                p = line_line_intersection(A[i], B[i], A[j], B[j])
                if point_on_segment(A[i], B[i], p) and point_on_segment(A[j], B[j], p):
                    seg_pts[i].append(p)
                    seg_pts[j].append(p)

    # 3) sort points along each segment and unique
    for i in range(n):
        if not valid[i]:
            continue
        base = A[i]
        seg_pts[i].sort(key=lambda p: (p - base).norm2())
        uniq = []
        for p in seg_pts[i]:
            if not uniq or not same_point(uniq[-1], p):
                uniq.append(p)
        seg_pts[i] = uniq

    # 4) global unique vertex list
    pts = []
    for i in range(n):
        pts.extend(seg_pts[i])

    pts.sort(key=lambda p: (p.x, p.y))
    uniq = []
    for p in pts:
        if not uniq or not same_point(uniq[-1], p):
            uniq.append(p)
    pts = uniq
    m = len(pts)
    if m == 0:
        print("0")
        return

    def idx_of(p: Point) -> int:
        for i in range(m):
            if same_point(pts[i], p):
                return i
        return -1

    # 5) adjacency: store best edges (dedup) by (to, cross)
    adj_best = [dict() for _ in range(m)]
    for i in range(n):
        if not valid[i]:
            continue
        arr = seg_pts[i]
        for j in range(len(arr) - 1):
            u = idx_of(arr[j])
            v = idx_of(arr[j + 1])
            length = (arr[j] - arr[j + 1]).norm()
            if length <= EPS:
                continue
            if abs(pts[u].angle() - pts[v].angle()) <= EPS:
                continue
            cross = crosses_up_ray(pts[u], pts[v])

            # undirected
            if (v, cross) not in adj_best[u] or adj_best[u][(v, cross)] < length:
                adj_best[u][(v, cross)] = length
            if (u, cross) not in adj_best[v] or adj_best[v][(u, cross)] < length:
                adj_best[v][(u, cross)] = length

    adj = [[] for _ in range(m)]
    for u in range(m):
        for (v, cross), length in adj_best[u].items():
            adj[u].append((v, length, cross))

    best = 0.0

    # 6) DP over both angle directions
    for direction in (0, 1):
        order = list(range(m))
        if direction == 0:
            order.sort(key=lambda i: (pts[i].angle(), pts[i].norm()))
        else:
            order.sort(key=lambda i: (-pts[i].angle(), pts[i].norm()))

        gpos = [0] * m
        for i, v in enumerate(order):
            gpos[v] = i

        for start in range(m):
            rel = [(gpos[v] - gpos[start] + m) % m for v in range(m)]
            at = [0] * m
            for v in range(m):
                at[rel[v]] = v

            dp0 = [-INF] * (m + 1)  # parity 0
            dp1 = [-INF] * (m + 1)  # parity 1
            dp0[0] = 0.0

            for i in range(m):
                v = at[i]
                for parity in (0, 1):
                    cur = dp0[i] if parity == 0 else dp1[i]
                    if cur <= -INF/2:
                        continue
                    for (to, length, cross) in adj[v]:
                        pto = rel[to]
                        if pto == 0:
                            pto = m
                        if pto > i:
                            np = parity ^ cross
                            val = cur + length
                            if np == 0:
                                if val > dp0[pto]:
                                    dp0[pto] = val
                            else:
                                if val > dp1[pto]:
                                    dp1[pto] = val

            best = max(best, dp1[m])  # odd parity => origin inside

    print(f"{best:.9f}")

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

---

If you want, I can also add a short proof sketch of “angle-monotone traversal ⇔ at most one intersection per ray” and why “odd parity ⇒ origin inside” is sufficient here.