CF70D.Professor's task

Once a walrus professor Plato asked his programming students to perform the following practical task.

The students had to implement such a data structure that would support a convex hull on some set of points S. The input to the program had q queries of two types:

1. Add a point with coordinates (x, y) into the set S. Note that in this case the convex hull of S could have changed, and could have remained the same.

2. Say whether a point with coordinates (x, y) belongs to an area limited by the convex hull, including the border.

All the students coped with the task. What about you?

曾有一位海象教授柏拉图，要求他的编程课学生完成如下实践任务：

学生需要实现一种数据结构，用于维护某个点集 $S$ 的凸包。程序的输入包含 $q$ 个查询，分为两类：

1. 将坐标为 $(x,\,y)$ 的点加入点集 $S$。注意：此操作可能导致 $S$ 的凸包发生变化，也可能保持不变。

2. 判断坐标为 $(x,\,y)$ 的点是否位于由凸包所围成的区域内（含边界）。

所有学生都成功完成了该任务。那么，你呢？

The first line contains an integer q (4 ≤ q ≤ 105).

Then follow q lines in the following way: "t x y", where t is the query type (1 or 2), and (x, y) are the coordinates of the point ( - 106 ≤ x, y ≤ 106, x and y are integers).

There is at least one query of type 2.

It is guaranteed that the three queries of the first type follow first and the points given in the queries form a non-degenerative triangle. Also all the points added in S are distinct.

第一行包含一个整数 $q$（$4 \le q \le 10^5$）。

接下来是 $q$ 行，每行格式为：“$t$ $x$ $y$”，其中 $t$ 是查询类型（$1$ 或 $2$），$(x, y)$ 是点的坐标（$-10^6 \le x, y \le 10^6$，且 $x$、$y$ 均为整数）。

至少存在一个类型为 $2$ 的查询。

保证前三个查询均为类型 $1$，且这些查询给出的三点构成一个非退化三角形。此外，所有加入集合 $S$ 的点互不相同。

For each query of the second type print one string containing "YES", if the point lies inside the convex hull or on its border. Otherwise, print "NO".

对于每个第二类查询，如果该点位于凸包内部或其边界上，则输出一行字符串“YES”；否则输出“NO”。