有一次,海象教授柏拉图要求他的编程学生执行以下实际任务。
学生们必须实现这样一个数据结构,该结构将支持某些点集 S 上的凸包。程序的输入有 q 个两种类型的查询:
1. 将坐标为 (x, y) 的点添加到集合 S 中。请注意,在这种情况下,S 的凸包可能已发生变化,也可能保持不变。
2. 判断坐标为(x,y)的点是否属于凸包所限定的区域,包括边界。
所有学生都完成了任务。你呢?
输入
第一行包含一个整数 q (4 ≤ q ≤ 105)。
然后按照以下方式跟踪 q 行:“t x y”,其中 t 是查询类型(1 或 2),(x, y) 是点的坐标(- 106 ≤ x,y ≤ 106,x 和 y 是整数)。
至少有一个类型 2 的查询。
保证第一类型的三个查询在先,并且查询中给出的点形成非退化三角形。此外,S 中添加的所有点都是不同的。
输出
对于第二类型的每个查询,如果该点位于凸包内部或其边界上,则打印一个包含“YES”的字符串。否则,打印“NO”。
示例
输入 #1
8 1 0 0 1 2 0 1 2 2 2 1 0 1 0 2 2 1 1 2 2 1 2 20 -1
输出 #1
YES YES YES NO