问题描述
[数据删除]正在进行一些奇怪的实验。
实验场地中有一个巨大的能量基地,可以视为一个半径为r,圆心在原点的圆。[数据删除]会在
其一侧(具体地,在x坐标轴以上的范围)布置一些装置(可以视为一个点)。装置距离原点的距离>r。
这些装置需要远程从基地获取能量,因此会存在一个特殊区域发生能量的传输。设圆与x轴的
两交点为 A,B,该装置的位置在 P,则传输范围为△ABP 与圆不重合的区域。注意传输范围包括
边界。
起初场上没有任何装置。[数据删除]可能会:
1.在(x,y)布置一个装置。装置的编号表示其发射的顺序。
2.拆掉装置 k。
3.试图调谐 i,j装
置,为之需要建立一个中继器(也可视为一个点)),中继器必须在 i,j的传输范围内。同时为了防止
干扰,中继器不得在其他装置的传输范围内且需要满足y 坐标> 0。中继器不能严格在基地内,但
可以在基地的边上。
对于所有3操作,[数据删除]想知道能不能架设中继器。注意如果能架设,3操作完后[数据删除]会
把中继器拆了,因此3操作之间互不影响。
输入格式
第一行两个数r,n,表示半径和操作个数。
接下来 n行,每行起始为一个字符串为build,destroy,query三者之一。
如果为build,表示操作1,后面跟两个整数表示建设装置的坐标。
如果为destroy,表示操作2,后面跟一个整数表示k。保证装置k当前没有被拆除。
如果为query,表示操作3,后面跟两个整数表示i,j,保证装置i,j当前没有被拆除且i≠j。
输出格式
对所有query操作,一行一个字符‘+/-'表示是否能建立中继器。
样例 1 输入
3 7 build -1 4 build 1 5 query 2 1 build -3 2 query 3 2 build -5 3 query 4 3样例 1 输出
+ - +数据规模与约定
$n≤ 1× 10^6,r≤ 10^9$。输入中给出的所有坐标(z;y)的范围都满足$ |x|≤ 10^9,0 < y ≤ 10^9$。同一 位置不会同时有2个装置。
Subtask1: $n≤ 100$(14pts)
Subtask2: $n,|x|,y,r ≤ 10^3$(13pts)
Subtask3:$ n,|x|, y,r≤ 10^5$(15pts)
Subtask4:$n ≤ 10^5$,至多50次 query 操作。(14pts)
Subtaskb:$n≤ 10^5$,无 destroy 操作。(12pts)
Subtask6:$n≤ 3×10^5$(10pts)
Subtask7:无特殊限制。(22pts)