CF1662O.Circular Maze

You are given a circular maze such as the ones shown in the figures.

Determine if it can be solved, i.e., if there is a path which goes from the center to the outside of the maze which does not touch any wall. The maze is described by $n$ walls. Each wall can be either circular or straight.

• Circular walls are described by a radius $r$, the distance from the center, and two angles $\theta_1, \theta_2$ describing the beginning and the end of the wall in the clockwise direction. Notice that swapping the two angles changes the wall.
• Straight walls are described by an angle $\theta$, the direction of the wall, and two radii $r_1 \lt r_2$ describing the beginning and the end of the wall.

Angles are measured in degrees; the angle $0$ corresponds to the upward pointing direction; and angles increase clockwise (hence the east direction corresponds to the angle $90$).

你将得到一个环形迷宫，如图中所示。

请判断该迷宫是否可解，即是否存在一条从迷宫中心通往外部的路径，且该路径不与任何墙壁相交。迷宫由 $n$ 面墙描述。每面墙可以是圆形的或直线形的。

• 圆形墙壁由半径 $r$（即其到中心的距离）以及两个角度 $\theta_1, \theta_2$ 描述，其中 $\theta_1$ 和 $\theta_2$ 表示该墙壁在顺时针方向上的起始角和终止角。注意：交换这两个角度将改变墙壁所表示的弧段。
• 直线形墙壁由一个角度 $\theta$（即该墙壁的方向）以及两个半径 $r_1 < r_2$ 描述，其中 $r_1$ 和 $r_2$ 表示该墙壁的起始半径和终止半径。

角度以度为单位；角度 $0^\circ$ 对应正上方方向；角度值按顺时针方向递增（因此正东方向对应角度 $90^\circ$）。

Each test contains multiple test cases. The first line contains an integer $t$ ($1\le t\le 20$) — the number of test cases. The descriptions of the $t$ test cases follow.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 5000$) — the number of walls.

Each of the following $n$ lines each contains a character (C for circular, and S for straight) and three integers:

• either $r, \theta_1, \theta_2$ ($1 \leq r \leq 20$ and $0 \leq \theta_1,\theta_2 \lt 360$ with $\theta_1 \neq \theta_2$) if the wall is circular,
• or $r_1$, $r_2$ and $\theta$ ($1 \leq r_1 \lt r_2 \leq 20$ and $0 \leq \theta \lt 360$) if the wall is straight.

It is guaranteed that circular walls do not overlap (but two circular walls may intersect at one or two points), and that straight walls do not overlap (but two straight walls may intersect at one point). However, circular and straight walls can intersect arbitrarily.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1\le t\le 20$），表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示墙壁的数量。

接下来的 $n$ 行，每行包含一个字符（C 表示圆形墙壁，S 表示直线墙壁）以及三个整数：

• 若墙壁为圆形，则给出 $r, \theta_1, \theta_2$（其中 $1 \leq r \leq 20$，且 $0 \leq \theta_1,\theta_2 \lt 360$，满足 $\theta_1 \neq \theta_2$）；
• 若墙壁为直线，则给出 $r_1$, $r_2$ 和 $\theta$（其中 $1 \leq r_1 \lt r_2 \leq 20$，且 $0 \leq \theta \lt 360$）。

保证所有圆形墙壁互不重叠（但两个圆形墙壁可能在一个或两个点处相交），且所有直线墙壁互不重叠（但两条直线墙壁可能在一个点处相交）。然而，圆形墙壁与直线墙壁之间可以任意相交。

For each test case, print YES if the maze can be solved and NO otherwise.

对于每个测试用例，如果迷宫可解，则输出 YES；否则输出 NO。

The two sample test cases correspond to the two mazes in the picture.

两个样例测试用例对应于图片中的两个迷宫。