← 返回题目列表

Codeforces · 856/E

E. 卫星

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

Real Cosmic Communications 是一个遥远星球上最大的电信公司,位于宇宙的最边缘。 RCC 发射通信卫星。

这颗行星位于宇宙的最边缘,因此它的形状是半个圆形。它的半径是r,其直径的两端是点A和B。线AB是宇宙的边缘,因此其中一个半平面不包含任何东西,既没有行星,也没有RCC卫星,也没有其他任何东西。我们这样介绍坐标:原点位于AB线段的中心,OX轴与AB线重合,行星完全在y>0半平面内。

卫星可以位于宇宙的任何一点,除了行星点。卫星永远不会位于宇宙边缘之外,也不位于边缘本身,也就是说,它们的坐标 y > 0。卫星天线的方向是覆盖与卫星顶点的角度,边缘指向 A 点和 B 点。我们将此区域称为卫星覆盖区域。

下图显示了卫星的坐标系和覆盖区域。

RCC 成立时,地球上还没有卫星。自那时起,发生了若干属于以下类型之一的事件:

1. 1 x y — 发射新卫星并将其放置到点 (x, y)。卫星永远不会移动并停留在发射点。让我们按照发射顺序将编号 i 分配给第 i 颗卫星,从一颗开始。
2. 2 i — 删除卫星号 i。
3. 3 i j — 尝试在卫星 i 和 j 之间创建通信信道。要创建通信通道,需要中继器。它不能位于行星内部,但可以位于其半圆边界或其上方。中继器必须位于卫星 i 和 j 的覆盖范围内。为避免信号干扰,不得位于任何其他卫星的覆盖范围内。当然,中继器必须在宇宙内部,它的坐标必须是y > 0。

每次尝试创建通信通道时,您都必须查明是否可行。

示例测试具有以下卫星位置:

输入

输入数据的第一行包含整数 r 和 n - 行星半径和事件数量 (1 ≤ r ≤ 109, 1 ≤ n ≤ 5·105)。

以下 n 行中的每一行以指定格式描述事件。

卫星坐标为整数,满足以下约束|x| ≤ 109, 0 < y ≤ 109。同时存在的两颗卫星不能占据同一点。每颗卫星到地球中心的距离严格大于 r。

保证类型2和类型3的事件仅涉及当前存在的卫星。对于类型 3 的所有事件,满足不等式 i ≠ j。

输出

对于类型 3 的每个事件,如果可以创建通信通道,则在单独的行上打印“YES”,如果不可能,则打印“NO”。

示例

输入 #1

5 8
1 -5 8
1 -4 8
1 -3 8
1 2 7
3 1 3
2 2
3 1 3
3 3 4

输出 #1

NO
YES
YES