Migrated from Lutece 2547 小兔养马

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小兔打算在他的农场养一些马，并用栅栏将马圈养起来。我们可以把农场看作一个二维坐标平面，把马看作平面上的不同点，把栅栏看作平面上的线段。

小兔会不时购入新的马，并将其放置在农场上某一指定位置。同时，每次购入一匹新的马，小兔都会重新修建所有栅栏，使得栅栏能将所有马围住，并且栅栏总长度最小。

小兔的农场上还有一个探测器，用于探测农场上的人员位置。一旦有人进入了栅栏围成的区域（包括边界），探测器就会拉响警报。

现在依次给出小兔购入马的记录以及探测器的记录，请对于每个探测器的记录给出是否拉响警报。

Input

第一行包含一个整数 $n\ (4 \le n \le 10^5)$，表示记录的数量。

接下来 $n$ 行，每行三个整数 $t,x,y\ (1\le t \le 2, -10^6 \le x,y \le 10^6)$，表示一条记录。

• 1 x y 表示小兔购入一匹新的马，并将其放置在 $(x,y)$ 处。
• 2 x y 表示探测器探测到 $(x,y)$ 处有人。

数据保证前三条记录一定是购入马的记录，且前三条记录中给出的位置不共线。所有购入的马的位置互不相同。

Output

对于每个探测器的记录，输出是否拉响警报，如果是输出 YES，否则输出 NO。

Samples

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

YES
YES
YES
NO

Resources

2021 UESTC ICPC Training for Math and Geometry