← 返回题目列表

Codeforces · 70/D

D. 教授的任务

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

有一次,海象教授柏拉图要求他的编程学生执行以下实际任务。

学生们必须实现这样一个数据结构,该结构将支持某些点集 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