← 返回题目列表

Codeforces · 1662/O

O. 圆形迷宫

中文机器翻译题面 查看原题

给你一个圆形迷宫,如图所示。

- 圆形墙由半径 $$$r$$$(距中心的距离)和两个角度 $$$\theta_1、\theta_2$$$ 描述,以顺时针方向描述墙的起点和终点。请注意,交换两个角度会改变墙壁。
- 直墙由角度 $$$\theta$$$、墙的方向以及描述墙的起点和终点的两个半径 $$$r_1 < r_2$$$ 来描述。

角度以度为单位;角度$$$0$$$对应于向上指向的方向;并且角度顺时针增加(因此东方向对应于角度$$$90$$$)。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$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 < 360$$$ 和 $$$\theta_1 \neq \theta_2$$$) 如果墙是圆形的,
- 或 $$$r_1$$$、$$$r_2$$$ 和 $$$\theta$$$ ($$$1 \leq r_1 < r_2 \leq 20$$$ 和 $$$0 \leq \theta < 360$$$) 如果墙是直的。

保证圆形墙不重叠(但两个圆形墙可能在一两个点相交),并且直墙不重叠(但两个直墙可能在一点相交)。然而,圆形墙和直墙可以任意相交。

输出

对于每个测试用例,如果可以解决迷宫,则打印 YES,否则打印 NO。

示例

输入 #1

2
5
C 1 180 90
C 5 250 230
C 10 150 140
C 20 185 180
S 1 20 180
6
C 1 180 90
C 5 250 230
C 10 150 140
C 20 185 180
S 1 20 180
S 5 10 0

输出 #1

YES
NO

注意

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