CF70D Professor's task

有一次，海象教授 Plato 给他的编程学生们布置了如下实践任务： 学生们必须实现一种数据结构，能够维护某个点集 $S$ 的凸包。程序将接收 $q$ 个操作，操作分为两类： 1. 向集合 $S$ 中加入一个坐标为 $(x, y)$ 的点。注意，每次插入后集合 $S$ 的凸包可能会发生变化，也可能不变。 2. 判断给定点 $(x, y)$ 是否在凸包内部（包含边界）。 所有学生都完成了这项任务。那么你能做到吗？

第一行包含一个整数 $q$（$4 \leq q \leq 10^{5}$）。 接下来的 $q$ 行，每行格式为“$t$ $x$ $y$”，其中 $t$ 表示操作类型（1 或 2），$(x, y)$ 为点的坐标（$-10^{6} \leq x, y \leq 10^{6}$，$x$和$y$均为整数）。 保证至少有一次类型为 2 的操作。 保证前面有三次类型 1 的操作，且给出的这三点构成了一个非退化三角形。所有插入到 $S$ 中的点都互不相同。

对于每个类型为 2 的操作，输出一行，如果查询点在凸包内部或边界上，输出“YES”；否则，输出“NO”。

由 ChatGPT 5 翻译