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

198. Get Out!
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Captain Faraway on his famous circular ship Kolobok is lost among the islands of the archipelago that he has just discovered. Now he wonders whether he can get out of there. Help him!

All islands in the archipelago can be composed of pieces that have circular form. You are given the map of archipelago and the position of captain. Find out whether captain can get out of there, i.e. can get as far from the point he is in the beginning as he likes.

Input

The first line contains N — the number of circular island parts (1 ≤ N ≤ 300). N lines follow, each containing xi, yi, ri — coordinates of center and radius of the i-th circle. All coordinates and radii are real. Objects may overlap with each other in arbitrary way. All objects are considered solid.

The last line of the input file contains three real numbers — coordinates of the center of Kolobok and its radius.

You may consider Kolobok to be the perfect circle and that it is in the free area in the beginning. Kolobok can move along any trajectory and is so strong that he can even touch islands, but no nonzero part of island must intersect Kolobok during his motion. You may assume that making calculations with the precision of 10-6 is satisfactory.

Output

Output YES if Kolobok can leave archipelago and NO if it cannot.

Sample test(s)

Input

Test #1

7
2 2 1.1
-2 2 1.1
2 -2 1.0
-2 -2 1.0
2 -5 1.0
0 -8 1.0
-2 -6 1.0
0 0 1

Test #2

5
2 2 1.1
-2 2 1.1
2 -2 1.0
-2 -2 1.0
0 -3 0.01
0 0 1

Output

Test #1

YES

Test #2

NO

<|response|>
1) Abridged problem statement
- You are given N solid circular obstacles (xi, yi, ri) and a circular ship (cx, cy, cr).
- The ship may move freely, may touch obstacles, but must never intersect them.
- Decide if the ship can move arbitrarily far from its start (escape to infinity). Print YES if it can, otherwise NO.

2) Key observations
- Minkowski sum reduction: Inflate every obstacle radius by the ship radius cr and move the coordinate system so the ship starts at the origin. Now the ship is a point at (0, 0) and obstacles are discs centered at (xi − cx, yi − cy) with radii (ri + cr). The start is guaranteed to be in free space.
- The origin is trapped iff the union of these inflated discs contains a closed loop encircling the origin (a barrier to infinity).
- A practical certificate is a cycle of pairwise-intersecting discs that winds around the origin. Viewed from the origin, each disc has a polar angle; along a chain of overlapping discs, the “visible angle” cannot jump by more than π. A loop that goes around the origin accumulates a total signed angle ≈ ±2π.
- Build a graph on discs: connect i and j if their inflated discs intersect. For each such pair, set edge weight w(i→j) to the minimal signed angular difference Δθ ∈ (−π, π] from angle(ci) to angle(cj), and w(j→i) = −Δθ. Then any enclosing loop yields a negative cycle with total weight < −π in at least one direction.
- Detect such a cycle with Floyd–Warshall; if any dist[i][i] < −π, the origin is enclosed → cannot escape.

3) Full solution approach
- Transform:
  - For each obstacle i: xi ← xi − cx, yi ← yi − cy, ri ← ri + cr.
  - Compute the polar angle θi of center i around the origin. The code below uses acos(x/|c|) and corrects the sign for negative y to obtain the full [0, 2π) angle (atan2 works equally well).
- Build a directed complete graph with infinities:
  - For each pair (i, j), if the inflated discs overlap/touch, i.e., |ci − cj| ≤ ri + rj (with a small tolerance):
    - Let Δ = θj − θi normalized into (−π, π].
    - Set w[i][j] = Δ and w[j][i] = −Δ.
  - Otherwise set w[i][j] = +∞ (no edge).
- Run Floyd–Warshall on w, relaxing with a tiny epsilon to absorb rounding:
  - w[i][j] = min(w[i][j], w[i][k] + w[k][j] + EPS).
- If any w[i][i] < −π, output NO (trapped). Otherwise output YES (can escape).
- Complexity: O(N^3) time, O(N^2) memory. With N ≤ 300 this is fine in C++.

Numerical notes
- Use EPS ≈ 1e−6 for both the overlap test and the relaxation step.
- Normalize angle differences into (−π, π].

4) C++ implementation
```cpp
#include <bits/stdc++.h>

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

const double PI = acos(-1);
const double eps = 1e-6;

int n;
vector<double> x, y, rad;
double cx, cy, cr;

void read() {
    cin >> n;
    x.resize(n);
    y.resize(n);
    rad.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> rad[i];
    }
    cin >> cx >> cy >> cr;
}

void solve() {
    // The idea is to check if the captain is enclosed by a cycle of overlapping
    // islands. We first transform the problem by centering at the captain's
    // position and expanding island radii by the captain's radius. This reduces
    // the captain to a point at origin.
    //
    // We then build a graph where islands are nodes. If two islands overlap (or
    // touch), we create directed edges between them with weights equal to the
    // signed angle between their centers as viewed from the origin.
    //
    // If there exists a cycle in this graph with non-zero total angle
    // (specifically, a negative cycle), it means the islands form a loop around
    // the origin, trapping the captain. We use Floyd-Warshall to find shortest
    // paths and check if any node has a negative cycle to itself.

    for(int i = 0; i < n; i++) {
        x[i] -= cx;
        y[i] -= cy;
        rad[i] += cr;
    }

    vector<vector<double>> dist(n, vector<double>(n, 0));
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            double center_dist_sq =
                (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
            double sum_rad_sq = (rad[i] + rad[j]) * (rad[i] + rad[j]);

            if(center_dist_sq + eps > sum_rad_sq) {
                dist[i][j] = 1e18;
                dist[j][i] = 1e18;
            } else {
                double alpha = acos(x[i] / sqrt(x[i] * x[i] + y[i] * y[i]));
                double beta = acos(x[j] / sqrt(x[j] * x[j] + y[j] * y[j]));
                if(y[i] < -eps) {
                    alpha = 2 * PI - alpha;
                }
                if(y[j] < -eps) {
                    beta = 2 * PI - beta;
                }

                double angle_diff = beta - alpha;
                if(angle_diff < 0) {
                    angle_diff += 2 * PI;
                }

                if(angle_diff > PI) {
                    angle_diff -= 2 * PI;
                }
                dist[i][j] = angle_diff;
                dist[j][i] = -angle_diff;
            }
        }
    }

    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j] + eps);
            }
        }
    }

    for(int i = 0; i < n; i++) {
        if(dist[i][i] < -PI) {
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << endl;
}

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 with detailed comments
Note: Python’s O(N^3) Floyd–Warshall may be slow for the largest N on tight time limits, but it illustrates the method clearly.

```python
import sys
import math

def can_escape(circles, ship):
    cx, cy, cr = ship
    n = len(circles)

    # 1) Minkowski sum and shift: ship becomes a point at origin.
    x = [0.0] * n
    y = [0.0] * n
    R = [0.0] * n
    for i, (xi, yi, ri) in enumerate(circles):
        x[i] = xi - cx
        y[i] = yi - cy
        R[i] = ri + cr

    # 2) Angles of centers as seen from origin in [0, 2π).
    theta = [math.atan2(y[i], x[i]) % (2.0 * math.pi) for i in range(n)]

    INF = 1e100
    EPS = 1e-6

    # 3) Build weight matrix.
    w = [[INF] * n for _ in range(n)]
    for i in range(n):
        w[i][i] = 0.0

    for i in range(n):
        xi, yi, ri = x[i], y[i], R[i]
        for j in range(i + 1, n):
            xj, yj, rj = x[j], y[j], R[j]
            dx = xi - xj
            dy = yi - yj
            dist2 = dx * dx + dy * dy
            sumR = ri + rj
            sumR2 = sumR * sumR

            # Intersect/touch if dist <= sumR (with a small tolerance).
            if dist2 <= sumR2 + EPS:
                diff = theta[j] - theta[i]
                # Normalize into (-π, π]
                diff = (diff + math.pi) % (2.0 * math.pi) - math.pi
                w[i][j] = diff
                w[j][i] = -diff

    # 4) Floyd–Warshall with tiny epsilon in relaxations.
    for k in range(n):
        wk = w[k]
        for i in range(n):
            wik = w[i][k]
            if wik >= INF / 2:
                continue
            wi = w[i]
            base = wik
            for j in range(n):
                cand = base + wk[j] + EPS
                if cand < wi[j]:
                    wi[j] = cand

    # 5) Negative cycle of magnitude ≳ 2π → trapped.
    for i in range(n):
        if w[i][i] < -math.pi:
            return False
    return True

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    circles = []
    for _ in range(n):
        xi = float(next(it)); yi = float(next(it)); ri = float(next(it))
        circles.append((xi, yi, ri))
    cx = float(next(it)); cy = float(next(it)); cr = float(next(it))

    print("YES" if can_escape(circles, (cx, cy, cr)) else "NO")

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

Summary
- Inflate obstacles by the ship radius and shift so the ship is a point at the origin.
- Connect overlapping discs; weight each directed edge by the minimal signed angular difference between their center directions.
- Floyd–Warshall detects enclosing cycles as dist[i][i] < −π.
- Answer NO if trapped (enclosed), otherwise YES.
