## 1. Abridged problem statement

Given two points `A` and `B` outside a circular crater with center `C` and radius `R`, find and output a shortest route from `A` to `B`.

The route may consist of straight segments and arcs of the crater circle. Moving inside the crater is possible only using an antigravitator, whose total usable distance is at most `D`. Thus, the total length of all route portions lying strictly inside the circle must not exceed `D`.

Output the route as at most `100` parts, each either:

- `S x1 y1 x2 y2` — a straight segment,
- `A x1 y1 x2 y2` — an arc of the crater circle between two endpoints.

Any shortest valid route is acceptable.

---

## 2. Detailed editorial

### Geometry model

We have a disk-shaped obstacle. Walking/flying along the boundary of the disk is free in the sense that it does not consume antigravitator fuel. Crossing the disk along a straight chord consumes fuel equal to the length of that chord.

The shortest route around or through a circle has a very restricted form:

1. If the straight segment `AB` does not enter the crater, then `AB` is optimal.
2. If `AB` enters the crater, but the chord length inside the crater is at most `D`, then `AB` is still optimal.
3. Otherwise, the route must touch the circle boundary and possibly travel along it and/or cut across it by a chord.

The solution considers both possible sides of going around the circle.

---

### Checking whether a segment enters the disk

For a segment `P0P1`, compute the closest point on the segment to the center `C`.

Let:

```text
d = P1 - P0
t = dot(C - P0, d) / |d|²
```

Clamp `t` into `[0, 1]`.

The closest point is:

```text
P0 + t d
```

If its distance to `C` is at least `R`, the segment does not enter the disk.

This is used by:

```cpp
seg_ok(p0, p1)
```

---

### Case 1: straight route is valid

If `AB` does not enter the disk, output:

```text
1
S A B
```

If it does enter the disk, compute the length of the chord cut by line `AB`.

Let `h` be the distance from the center to the line `AB`.

Then the chord length inside the circle is:

```text
2 * sqrt(R² - h²)
```

If this length is at most `D`, the straight segment is still feasible and optimal.

---

### Tangents from an external point to the circle

For an outside point `P`, let:

```text
d = |P - C|
psi = angle of vector C -> P
gamma = acos(R / d)
```

The two tangent points on the circle have angular positions:

```text
psi + gamma
psi - gamma
```

For each side `s = +1` or `s = -1`, the algorithm chooses compatible tangent points:

```text
A tangent angle = psiA + s * gammaA
B tangent angle = psiB - s * gammaB
```

The boundary arc between them is traveled in direction `s`.

The angular size of that arc is:

```text
Phi = s * (angleB - angleA) modulo 2π
```

The pure outside detour length is:

```text
|A - TA| + R * Phi + |TB - B|
```

where `TA` and `TB` are the tangent points.

This route is always valid, so it provides an initial answer candidate.

---

### Using the fuel as one chord

Suppose we replace part of the boundary arc by a chord through the disk.

A chord of length `D` in a circle of radius `R` subtends central angle:

```text
thetaD = 2 * asin(D / (2R))
```

The important observation is:

> It is never worse to spend the fuel on one chord instead of splitting it among several chords.

Also, all chords of the same length subtend the same angle and save the same amount of arc length, regardless of where they are placed.

So, if:

```text
thetaD <= Phi
```

then we can replace a sub-arc of angular length `thetaD` by a chord of length `D`.

For convenience, the solution places this chord immediately after the tangent point from `A`.

The route becomes:

```text
A -> TA       segment
TA -> P       chord, length D
P -> TB       circle arc
TB -> B       segment
```

Its length is:

```text
|A - TA| + D + R * (Phi - thetaD) + |TB - B|
```

This is another candidate.

---

### When the chord angle is larger than the tangent arc

Sometimes `thetaD > Phi`.

Then the optimal route may not use the two tangent points anymore. Instead, it can have the form:

```text
A -> P -> Q -> B
```

where:

- `P` and `Q` lie on the circle,
- `PQ` is a chord of length `D`,
- the angular difference between `P` and `Q` is `thetaD`,
- `AP` and `QB` must not enter the disk.

For a fixed side `s`, if `P` has angle `alpha`, then:

```text
Q angle = alpha + s * thetaD
```

The route length is:

```text
|A - P| + D + |Q - B|
```

Now only one variable remains: `alpha`.

The feasible interval for `alpha` is determined by visibility from `A` and `B`.

A point on the circle is visible from an outside point if it lies between that point's two tangent points.

Therefore:

```text
alpha must lie within A's visible tangent interval
alpha + s * thetaD must lie within B's visible tangent interval
```

The solution computes the intersection of these angular intervals and then minimizes the one-variable function by ternary search.

Although the function is geometrically simple and unimodal on the feasible interval, the implementation also checks `seg_ok` for safety.

---

### Candidate selection

For both directions around the circle, the solution considers:

1. Pure tangent-arc-tangent detour.
2. Tangent-chord-arc-tangent route.
3. Free chord route `A -> P -> Q -> B`.

The shortest candidate is printed.

---

### Complexity

All operations are constant-time geometry computations plus a fixed `200`-iteration ternary search for each of two sides.

Time complexity:

```text
O(1)
```

Memory usage:

```text
O(1)
```

---

## 3. Provided C++ solution with detailed comments

```cpp
#include <bits/stdc++.h>
// Include the whole C++ standard library.

using namespace std;

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

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

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

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

// Coordinate type used by the geometry code.
using coord_t = double;

// 2D point/vector structure.
struct Point {
    // Epsilon for floating-point comparisons.
    static constexpr coord_t eps = 1e-9;

    // Pi constant.
    static inline const coord_t PI = acos((coord_t)-1.0);

    // Cartesian coordinates.
    coord_t x, y;

    // Constructor. Defaults to the origin.
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    // Vector addition.
    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }

    // Vector subtraction.
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }

    // Multiplication by scalar.
    Point operator*(coord_t c) const { return Point(x * c, y * c); }

    // Division by scalar.
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    // Dot product.
    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }

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

    // Exact equality. Mostly unused in this solution.
    bool operator==(const Point& p) const { return x == p.x && y == p.y; }

    // Exact inequality.
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }

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

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

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

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

    // Squared vector length.
    coord_t norm2() const { return x * x + y * y; }

    // Vector length.
    coord_t norm() const { return sqrt(norm2()); }

    // Polar angle.
    coord_t angle() const { return atan2(y, x); }

    // Rotate vector counterclockwise by angle a.
    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    // Perpendicular vector rotated by 90 degrees.
    Point perp() const { return Point(-y, x); }

    // Unit vector in same direction.
    Point unit() const { return *this / norm(); }

    // Unit normal.
    Point normal() const { return perp().unit(); }

    // Projection of p onto this vector.
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }

    // Reflection of p with respect to line through origin in direction this vector.
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    // Output point.
    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }

    // Input point.
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    // Orientation test: +1 left turn, -1 right turn, 0 collinear.
    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;
        }
    }

    // Check whether p lies on segment ab.
    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;
    }

    // Check whether p is inside or on triangle abc.
    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);
    }

    // Intersection point of two non-parallel lines.
    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));
    }

    // Check whether two vectors are collinear.
    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    // Circumcenter of triangle abc.
    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
        );
    }

    // Signed area contribution of a circular arc.
    // Not used by this problem.
    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;
    }

    // Intersection points of two circles.
    // Not used by the main solution.
    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};
    }

    // Intersection of a ray and a segment.
    // Not used by the main solution.
    friend optional<Point> intersect_ray_segment(
        const Point& ray_start, const Point& ray_through, const Point& seg_a,
        const Point& seg_b
    ) {
        Point ray_dir = ray_through - ray_start;
        if(ray_dir.norm2() < Point::eps) {
            return {};
        }
        Point seg_dir = seg_b - seg_a;
        coord_t denom = ray_dir ^ seg_dir;
        if(fabs(denom) < eps) {
            return {};
        }
        coord_t t = ((seg_a - ray_start) ^ seg_dir) / denom;
        if(t < eps) {
            return {};
        }
        coord_t s = ((seg_a - ray_start) ^ ray_dir) / denom;
        if(s < eps || s > 1 - eps) {
            return {};
        }
        return ray_start + ray_dir * t;
    }
};

// Global input data.
Point A, B, center;
coord_t R, D;

// Read input.
void read() { cin >> A >> B >> center >> R >> D; }

// One output route part.
struct Part {
    char type; // 'S' for segment, 'A' for arc.
    Point a, b; // endpoints.
};

void solve() {
    // Large value used as infinity.
    const coord_t INF = 1e18;

    // Return the point on the crater circle with polar angle ang.
    auto on_circle = [&](coord_t ang) {
        return center + Point(cos(ang), sin(ang)) * R;
    };

    // Check whether segment p0-p1 does not enter the disk.
    auto seg_ok = [&](const Point& p0, const Point& p1) {
        Point d = p1 - p0;          // Segment direction vector.
        coord_t dn = d.norm2();     // Squared segment length.
        coord_t t = 0;              // Closest-point parameter.

        if(dn > Point::eps) {
            // Projection of center onto the segment's supporting line.
            t = ((center - p0) * d) / dn;

            // Clamp projection to the actual segment.
            t = max((coord_t)0, min((coord_t)1, t));
        }

        // Closest point on the segment to the circle center.
        Point cl = p0 + d * t;

        // Segment is okay if closest distance is at least the radius.
        return (cl - center).norm() >= R - 1e-7;
    };

    // Print a route, removing zero-length pieces.
    auto print = [&](const vector<Part>& parts) {
        vector<Part> p;

        // Discard degenerate parts.
        for(const auto& q: parts) {
            if((q.a - q.b).norm() > 1e-9) {
                p.push_back(q);
            }
        }

        // Print with fixed precision.
        cout << fixed << setprecision(8);

        // Number of parts.
        cout << p.size() << '\n';

        // Print every route part.
        for(const auto& q: p) {
            cout << q.type << ' ' << q.a.x << ' ' << q.a.y << ' ' << q.b.x
                 << ' ' << q.b.y << '\n';
        }
    };

    // If the straight segment does not enter the crater, it is optimal.
    if(seg_ok(A, B)) {
        print({{'S', A, B}});
        return;
    }

    // Distance from circle center to line AB.
    coord_t h = fabs((B - A) ^ (center - A)) / (B - A).norm();

    // Length of chord cut by AB inside the circle.
    coord_t chord_ab = 2 * sqrt(max((coord_t)0, R * R - h * h));

    // If the antigravitator can cover that chord, straight path is feasible.
    if(chord_ab <= D + 1e-9) {
        print({{'S', A, B}});
        return;
    }

    // Distances from center to A and B.
    coord_t dA = (A - center).norm(), dB = (B - center).norm();

    // Lengths of tangent segments from A and B to the circle.
    coord_t tA = sqrt(dA * dA - R * R), tB = sqrt(dB * dB - R * R);

    // Polar angles of vectors center->A and center->B.
    coord_t psiA = (A - center).angle(), psiB = (B - center).angle();

    // Angular offsets to tangent points.
    coord_t gA = acos(R / dA), gB = acos(R / dB);

    // Central angle subtended by a chord of length D.
    coord_t theta_d = 2 * asin(min((coord_t)1, D / (2 * R)));

    // Best found route length.
    coord_t best_len = INF;

    // Best found route parts.
    vector<Part> best;

    // Try to improve the answer.
    auto consider = [&](coord_t len, const vector<Part>& parts) {
        if(len < best_len) {
            best_len = len;
            best = parts;
        }
    };

    // Try both sides of the circle.
    for(int s: {1, -1}) {
        // Tangent angle from A for this side.
        coord_t a1 = psiA + s * gA;

        // Tangent angle to B for this side.
        coord_t a2 = psiB - s * gB;

        // Angular size of the boundary arc traveled in direction s.
        coord_t Phi = fmod(s * (a2 - a1), 2 * Point::PI);

        // Normalize to [0, 2pi).
        if(Phi < 0) {
            Phi += 2 * Point::PI;
        }

        // Tangent points.
        Point Ta = on_circle(a1), Tb = on_circle(a2);

        // Candidate 1: pure tangent + boundary arc + tangent route.
        consider(
            tA + tB + R * Phi,
            {{'S', A, Ta}, {'A', Ta, Tb}, {'S', Tb, B}}
        );

        // Candidate 2: replace part of that boundary arc by a chord of length D.
        if(theta_d <= Phi + 1e-12) {
            // Endpoint of the chord after leaving Ta.
            Point P2 = on_circle(a1 + s * theta_d);

            // Route: A -> Ta, Ta -> P2 as chord, P2 -> Tb along arc, Tb -> B.
            consider(
                tA + tB + R * (Phi - theta_d) + D,
                {{'S', A, Ta}, {'S', Ta, P2}, {'A', P2, Tb}, {'S', Tb, B}}
            );
        }

        // Cost of free-chord route A -> P -> Q -> B,
        // where angle(Q) = angle(P) + s * theta_d.
        auto g = [&](coord_t al) -> coord_t {
            Point P = on_circle(al), Q = on_circle(al + s * theta_d);

            // Outer segments must not enter the crater.
            if(!seg_ok(A, P) || !seg_ok(Q, B)) {
                return INF;
            }

            // Total geometric length.
            return (A - P).norm() + D + (Q - B).norm();
        };

        // For Q to be visible from B, alpha must be near psiB - s*theta_d.
        coord_t cB = psiB - s * theta_d;

        // Signed angular difference between that center and psiA.
        coord_t d = atan2(sin(cB - psiA), cos(cB - psiA));

        // Intersect visibility interval from A with shifted visibility interval from B.
        coord_t lo = max(-gA, d - gB), hi = min(gA, d + gB);

        // If there is a feasible angular interval, minimize over it.
        if(lo <= hi) {
            // Convert relative angles to absolute angles.
            lo += psiA;
            hi += psiA;

            // Ternary search on the one-dimensional feasible interval.
            for(int it = 0; it < 200; it++) {
                coord_t m1 = lo + (hi - lo) / 3;
                coord_t m2 = hi - (hi - lo) / 3;

                if(g(m1) < g(m2)) {
                    hi = m2;
                } else {
                    lo = m1;
                }
            }

            // Best angle after ternary search.
            coord_t al = (lo + hi) / 2;

            // Cost at this angle.
            coord_t c = g(al);

            // If feasible, consider this route.
            if(c < INF / 2) {
                Point P = on_circle(al), Q = on_circle(al + s * theta_d);
                consider(c, {{'S', A, P}, {'S', P, Q}, {'S', Q, B}});
            }
        }
    }

    // Print the shortest candidate.
    print(best);
}

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

    // Only one test case.
    int T = 1;

    // Solve all test cases.
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python solution with detailed comments

```python
import sys
import math


# Small epsilon for floating-point comparisons.
EPS = 1e-9

# Pi constant.
PI = math.pi

# Large number used as infinity.
INF = 10**100


class Point:
    """Simple 2D point/vector class."""

    def __init__(self, x=0.0, y=0.0):
        # Store coordinates as floats.
        self.x = float(x)
        self.y = float(y)

    def __add__(self, other):
        # Vector addition.
        return Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        # Vector subtraction.
        return Point(self.x - other.x, self.y - other.y)

    def __mul__(self, value):
        # If multiplying by another point, return dot product.
        if isinstance(value, Point):
            return self.x * value.x + self.y * value.y

        # Otherwise multiply by scalar.
        return Point(self.x * value, self.y * value)

    def __rmul__(self, value):
        # Scalar multiplication from the left.
        return self.__mul__(value)

    def __truediv__(self, value):
        # Divide vector by scalar.
        return Point(self.x / value, self.y / value)

    def cross(self, other):
        # 2D cross product.
        return self.x * other.y - self.y * other.x

    def norm2(self):
        # Squared Euclidean length.
        return self.x * self.x + self.y * self.y

    def norm(self):
        # Euclidean length.
        return math.sqrt(self.norm2())

    def angle(self):
        # Polar angle of the vector.
        return math.atan2(self.y, self.x)


def dist(a, b):
    # Distance between two points.
    return (a - b).norm()


def main():
    # Read all numbers from standard input.
    data = list(map(float, sys.stdin.read().split()))

    # First line: coordinates of A and B.
    xa, ya, xb, yb = data[0:4]

    # Second line: center and radius.
    xc, yc, R = data[4:7]

    # Third line: fuel distance.
    D = data[7]

    # Build point objects.
    A = Point(xa, ya)
    B = Point(xb, yb)
    center = Point(xc, yc)

    def on_circle(angle):
        """
        Return the point on the crater circle corresponding to polar angle
        measured from the center.
        """
        return center + Point(math.cos(angle), math.sin(angle)) * R

    def seg_ok(p0, p1):
        """
        Return True if segment p0-p1 does not enter the disk.
        Touching the boundary is allowed.
        """
        # Segment vector.
        d = p1 - p0

        # Squared segment length.
        dn = d.norm2()

        # Parameter of closest point to center.
        t = 0.0

        if dn > EPS:
            # Project center onto the supporting line.
            t = ((center - p0) * d) / dn

            # Clamp projection to the finite segment.
            t = max(0.0, min(1.0, t))

        # Closest point on segment to center.
        closest = p0 + d * t

        # Segment is outside if closest distance is at least R.
        return (closest - center).norm() >= R - 1e-7

    def print_route(parts):
        """
        Print route parts, removing zero-length pieces.
        Each part is stored as (type, point1, point2).
        """
        filtered = []

        # Remove degenerate parts.
        for typ, p, q in parts:
            if dist(p, q) > 1e-9:
                filtered.append((typ, p, q))

        # Print number of parts.
        print(len(filtered))

        # Print each part.
        for typ, p, q in filtered:
            print(
                f"{typ} "
                f"{p.x:.8f} {p.y:.8f} "
                f"{q.x:.8f} {q.y:.8f}"
            )

    # If direct segment does not enter crater, it is the shortest route.
    if seg_ok(A, B):
        print_route([("S", A, B)])
        return

    # Distance from center to line AB.
    h = abs((B - A).cross(center - A)) / dist(A, B)

    # Length of the chord of the circle cut by line AB.
    chord_ab = 2.0 * math.sqrt(max(0.0, R * R - h * h))

    # If fuel is enough for the direct crossing, direct segment is optimal.
    if chord_ab <= D + 1e-9:
        print_route([("S", A, B)])
        return

    # Distances from center to A and B.
    dA = dist(A, center)
    dB = dist(B, center)

    # Lengths of tangent segments.
    tA = math.sqrt(dA * dA - R * R)
    tB = math.sqrt(dB * dB - R * R)

    # Polar angles of A and B with respect to center.
    psiA = (A - center).angle()
    psiB = (B - center).angle()

    # Angular offsets to tangent points.
    gA = math.acos(R / dA)
    gB = math.acos(R / dB)

    # Central angle subtended by chord of length D.
    # Here D < direct chord length <= 2R, because otherwise we returned above.
    theta_d = 2.0 * math.asin(min(1.0, D / (2.0 * R)))

    # Best answer found so far.
    best_len = INF
    best_parts = []

    def consider(length, parts):
        """Update global best route if this candidate is shorter."""
        nonlocal best_len, best_parts

        if length < best_len:
            best_len = length
            best_parts = parts

    # Try both clockwise and counterclockwise sides.
    for s in (1, -1):
        # Tangent point angle from A on this side.
        a1 = psiA + s * gA

        # Tangent point angle to B on this side.
        a2 = psiB - s * gB

        # Angular size of boundary arc from a1 to a2 in direction s.
        Phi = math.fmod(s * (a2 - a1), 2.0 * PI)

        # Normalize to non-negative.
        if Phi < 0.0:
            Phi += 2.0 * PI

        # Actual tangent points.
        Ta = on_circle(a1)
        Tb = on_circle(a2)

        # Candidate 1:
        # A -> Ta, then boundary arc Ta -> Tb, then Tb -> B.
        consider(
            tA + R * Phi + tB,
            [("S", A, Ta), ("A", Ta, Tb), ("S", Tb, B)]
        )

        # Candidate 2:
        # Replace a part of this arc by a chord of length D.
        if theta_d <= Phi + 1e-12:
            # Endpoint after crossing the chord.
            P2 = on_circle(a1 + s * theta_d)

            # Length = tangents + chord + remaining arc.
            consider(
                tA + D + R * (Phi - theta_d) + tB,
                [("S", A, Ta), ("S", Ta, P2), ("A", P2, Tb), ("S", Tb, B)]
            )

        def free_chord_cost(alpha):
            """
            Cost of route A -> P -> Q -> B,
            where angle(P)=alpha and angle(Q)=alpha+s*theta_d.
            """
            P = on_circle(alpha)
            Q = on_circle(alpha + s * theta_d)

            # Outer segments must be outside the disk.
            if not seg_ok(A, P):
                return INF

            if not seg_ok(Q, B):
                return INF

            # Total length.
            return dist(A, P) + D + dist(Q, B)

        # For Q to be visible from B:
        # alpha + s*theta_d must be within B's tangent interval.
        # Therefore alpha is centered near psiB - s*theta_d.
        cB = psiB - s * theta_d

        # Signed shortest angular difference between cB and psiA.
        delta = math.atan2(math.sin(cB - psiA), math.cos(cB - psiA))

        # Intersect A-visible interval [-gA, gA] with shifted B-visible interval.
        lo = max(-gA, delta - gB)
        hi = min(gA, delta + gB)

        # Candidate 3:
        # If feasible, minimize A -> P -> Q -> B over alpha.
        if lo <= hi:
            # Convert relative angles to absolute angles.
            lo += psiA
            hi += psiA

            # Ternary search over the feasible interval.
            for _ in range(200):
                m1 = lo + (hi - lo) / 3.0
                m2 = hi - (hi - lo) / 3.0

                if free_chord_cost(m1) < free_chord_cost(m2):
                    hi = m2
                else:
                    lo = m1

            # Best alpha.
            alpha = (lo + hi) / 2.0

            # Candidate cost.
            cost = free_chord_cost(alpha)

            # If feasible, save route.
            if cost < INF / 2:
                P = on_circle(alpha)
                Q = on_circle(alpha + s * theta_d)

                consider(
                    cost,
                    [("S", A, P), ("S", P, Q), ("S", Q, B)]
                )

    # Output shortest route found.
    print_route(best_parts)


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

---

## 5. Compressed editorial

Check if the direct segment `AB` is feasible. If it does not intersect the disk, output it. If it intersects the disk but the chord length inside the disk is at most `D`, also output it.

Otherwise, the shortest route must interact with the circle boundary. For each of the two sides of the circle, compute tangent points from `A` and `B`. The pure detour is:

```text
A -> tangent from A -> circle arc -> tangent to B -> B
```

This is always a valid candidate.

If a chord of length `D` subtends angle:

```text
theta = 2 asin(D / 2R)
```

and this angle fits inside the tangent-to-tangent arc, replace that much arc by one chord. This gives another candidate.

If the chord angle is too large for the tangent arc, use route:

```text
A -> P -> Q -> B
```

where `P` and `Q` are on the circle and `PQ` is a chord of length `D`. For each side, set:

```text
angle(Q) = angle(P) ± theta
```

The feasible angles for `P` are those visible from `A` and whose corresponding `Q` is visible from `B`. Intersect these angular intervals and minimize the route length by ternary search.

Try both sides and print the shortest route found.