#P18511. Master of Both V
Master of Both V
Master of Both V
陈教授精通数据结构与计算几何。最近,他向 Putata 和 Budada 讲解了凸多边形的定义:凸多边形是一个简单多边形,其所有内角都严格小于 。 简单多边形要求顶点两两不同,任意两条边不相交,只有相邻两条边可以在公共端点处相交。
两人解决了凸性判定问题,陈教授又提出了更进一步的任务。维护一个初始为空的线段多重集合 ,支持以下操作:
+ px py qx qy:向 中加入端点为 、 的线段。- i:删除本测试用例第 次操作加入的线段。保证第 次操作是插入,且对应的这一份线段当前仍在集合中。
每次操作后,回答是否存在一个凸多边形 ,满足所有输入线段都完整包含在它的某一条边上。
形式化地,设 的顶点按逆时针顺序为 。对每条 ,都存在 ,使得
线段 的含义是 上每一点都属于 。多条输入线段可以位于同一条多边形边上,也可以互相重合;没有要求输入线段端点必须是多边形顶点。
输入格式
第一行包含测试用例数 ()。每个测试用例的第一行包含操作数 (),随后 行各包含一个上述格式的操作,操作符为 + 或 -。
对于插入操作,四个坐标均为整数,满足 ,保证两个端点不同。
对于删除操作,;保证它引用的是此前的插入操作,并且对应的这一份线段当前仍然存在。编号是操作编号,不是第几个插入。
保证所有测试用例的 之和不超过 。
输出格式
每个测试用例输出一行长度恰为 的 0、1 字符串。第 个字符为 1 表示第 次操作后存在满足条件的凸多边形,否则为 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