A15042. Circular Maze

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 < 360$ with $\theta_1 \neq \theta_2$ ) if the wall is circular,
- or $r_1$ , $r_2$ and $\theta$ ( $1 \leq r_1 < r_2 \leq 20$ and $0 \leq \theta < 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.

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

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

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