## 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. 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 = double;

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};
    }

    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;
    }
};

Point A, B, center;
coord_t R, D;

void read() { cin >> A >> B >> center >> R >> D; }

struct Part {
    char type;
    Point a, b;
};

void solve() {
    // We travel from A to B; the disc may be entered, but the total length of
    // route lying inside it must not exceed the fuel budget D. If the straight
    // segment A-B stays outside the disc, or the chord it cuts through the disc
    // has length at most D, then that single segment is already the answer.
    //
    // Otherwise the optimum is a taut path that detours around the crater on
    // one of the two sides. Around a convex obstacle a taut path leaves A along
    // a tangent, hugs the boundary, and reaches B along a tangent. The fuel
    // lets us replace one sub-arc of the boundary by a straight chord. A chord
    // of length D always subtends the same central angle 2*asin(D/2R), so the
    // saving (arc length minus the chord) is identical wherever the chord sits,
    // and one chord is never worse than splitting the budget into several. Thus
    // while the cut-out arc still fits inside the tangent-to-tangent arc Phi,
    // the route is tangent, chord of length D, remaining arc, tangent, and we
    // are free to place the chord right after A's tangent point.
    //
    // When D is large enough that the chord would subtend more than Phi, the
    // boundary no longer pins the touch points: the path degenerates to
    // A -> P -> Q -> B where P and Q sit on the circle exactly the chord angle
    // apart and the two outer segments must not re-enter the disc. There we
    // minimise |A-P| + D + |Q-B| over the single free angle by a dense scan
    // refined with ternary search, treating angles whose outer segments clip
    // the disc as infeasible.
    //
    // We build all three shapes (pure detour, tangent+chord+arc, and the free
    // two-tangent chord) for both sides and keep the shortest. Each emitted arc
    // spans less than 180 degrees, so naming only its endpoints is unambiguous.

    const coord_t INF = 1e18;

    auto on_circle = [&](coord_t ang) {
        return center + Point(cos(ang), sin(ang)) * R;
    };

    auto seg_ok = [&](const Point& p0, const Point& p1) {
        Point d = p1 - p0;
        coord_t dn = d.norm2();
        coord_t t = 0;
        if(dn > Point::eps) {
            t = ((center - p0) * d) / dn;
            t = max((coord_t)0, min((coord_t)1, t));
        }
        Point cl = p0 + d * t;
        return (cl - center).norm() >= R - 1e-7;
    };

    auto print = [&](const vector<Part>& parts) {
        vector<Part> p;
        for(const auto& q: parts) {
            if((q.a - q.b).norm() > 1e-9) {
                p.push_back(q);
            }
        }

        cout << fixed << setprecision(8);
        cout << p.size() << '\n';
        for(const auto& q: p) {
            cout << q.type << ' ' << q.a.x << ' ' << q.a.y << ' ' << q.b.x
                 << ' ' << q.b.y << '\n';
        }
    };

    if(seg_ok(A, B)) {
        print({{'S', A, B}});
        return;
    }

    coord_t h = fabs((B - A) ^ (center - A)) / (B - A).norm();
    coord_t chord_ab = 2 * sqrt(max((coord_t)0, R * R - h * h));
    if(chord_ab <= D + 1e-9) {
        print({{'S', A, B}});
        return;
    }

    coord_t dA = (A - center).norm(), dB = (B - center).norm();
    coord_t tA = sqrt(dA * dA - R * R), tB = sqrt(dB * dB - R * R);
    coord_t psiA = (A - center).angle(), psiB = (B - center).angle();
    coord_t gA = acos(R / dA), gB = acos(R / dB);
    coord_t theta_d = 2 * asin(min((coord_t)1, D / (2 * R)));

    coord_t best_len = INF;
    vector<Part> best;
    auto consider = [&](coord_t len, const vector<Part>& parts) {
        if(len < best_len) {
            best_len = len;
            best = parts;
        }
    };

    for(int s: {1, -1}) {
        coord_t a1 = psiA + s * gA;
        coord_t a2 = psiB - s * gB;
        coord_t Phi = fmod(s * (a2 - a1), 2 * Point::PI);
        if(Phi < 0) {
            Phi += 2 * Point::PI;
        }

        Point Ta = on_circle(a1), Tb = on_circle(a2);

        consider(
            tA + tB + R * Phi, {{'S', A, Ta}, {'A', Ta, Tb}, {'S', Tb, B}}
        );

        if(theta_d <= Phi + 1e-12) {
            Point P2 = on_circle(a1 + s * theta_d);
            consider(
                tA + tB + R * (Phi - theta_d) + D,
                {{'S', A, Ta}, {'S', Ta, P2}, {'A', P2, Tb}, {'S', Tb, B}}
            );
        }

        auto g = [&](coord_t al) -> coord_t {
            Point P = on_circle(al), Q = on_circle(al + s * theta_d);
            if(!seg_ok(A, P) || !seg_ok(Q, B)) {
                return INF;
            }
            return (A - P).norm() + D + (Q - B).norm();
        };

        coord_t cB = psiB - s * theta_d;
        coord_t d = atan2(sin(cB - psiA), cos(cB - psiA));
        coord_t lo = max(-gA, d - gB), hi = min(gA, d + gB);
        if(lo <= hi) {
            lo += psiA;
            hi += psiA;
            for(int it = 0; it < 200; it++) {
                coord_t m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
                if(g(m1) < g(m2)) {
                    hi = m2;
                } else {
                    lo = m1;
                }
            }

            coord_t al = (lo + hi) / 2, c = g(al);
            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(best);
}

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

    int T = 1;
    // cin >> T;
    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.
