#P18511. Master of Both V

Master of Both V

Master of Both V

陈教授精通数据结构与计算几何。最近,他向 Putata 和 Budada 讲解了凸多边形的定义:凸多边形是一个简单多边形,其所有内角都严格小于 π\pi。 简单多边形要求顶点两两不同,任意两条边不相交,只有相邻两条边可以在公共端点处相交。

两人解决了凸性判定问题,陈教授又提出了更进一步的任务。维护一个初始为空的线段多重集合 SS,支持以下操作:

  • + px py qx qy:向 SS 中加入端点为 (px,py)(p_x,p_y)、(qx,qy)(q_x,q_y) 的线段。
  • - i:删除本测试用例第 ii 次操作加入的线段。保证第 ii 次操作是插入,且对应的这一份线段当前仍在集合中。

每次操作后,回答是否存在一个凸多边形 CC,满足所有输入线段都完整包含在它的某一条边上。

形式化地,设 CC 的顶点按逆时针顺序为 p0,p1,…,pk−1p_0,p_1,\ldots,p_{k-1}。对每条 u∈Su\in S,都存在 j∈{0,1,…,k−1}j\in\{0,1,\ldots,k-1\},使得

u⊆pjp(j+1) mod k‾.u\subseteq\overline{p_jp_{(j+1)\bmod k}}.

线段 e⊆fe\subseteq f 的含义是 ee 上每一点都属于 ff。多条输入线段可以位于同一条多边形边上,也可以互相重合;没有要求输入线段端点必须是多边形顶点。

输入格式

第一行包含测试用例数 tt(1≤t≤5⋅1051\le t\le5\cdot10^5)。每个测试用例的第一行包含操作数 nn(1≤n≤5⋅1051\le n\le5\cdot10^5),随后 nn 行各包含一个上述格式的操作,操作符为 + 或 -。

对于插入操作,四个坐标均为整数,满足 −109≤px,py,qx,qy≤109-10^9\le p_x,p_y,q_x,q_y\le10^9,保证两个端点不同。

对于删除操作,1≤i≤n1\le i\le n;保证它引用的是此前的插入操作,并且对应的这一份线段当前仍然存在。编号是操作编号,不是第几个插入。

保证所有测试用例的 nn 之和不超过 5⋅1055\cdot10^5。

输出格式

每个测试用例输出一行长度恰为 nn 的 0、1 字符串。第 ii 个字符为 1 表示第 ii 次操作后存在满足条件的凸多边形,否则为 0。

空集可以选择任意凸多边形,答案为 1。全部线段共线时,可以让它们处于同一条较长的多边形边上。

完整原样例

4
8
+ 0 0 1 0
+ 5 5 1 3
+ 2 0 2 1
+ 9 7 6 2
+ 1 2 2 2
- 4
+ 0 1 0 2
- 2
5
+ 0 0 1 1
+ 0 1 1 2
+ 0 2 1 3
- 2
+ 1 1 10 10
4
+ 0 0 1 1
+ 0 0 1 0
+ 0 0 0 1
- 1
4
+ 0 0 1 1
+ 0 0 1 1
- 1
- 2
11000001
11011
1101
1111