[USACO15FEB] Fencing the Herd G

题目描述

Farmer John 需要你帮助他决定在哪里建造形状是一条无限长的直线的栅栏来限制他的牛的活动。他选出了几个可能的建造栅栏的位置,你需要帮助他判断哪些栅栏是有用的。一个栅栏是有用的当且仅当所有奶牛都在栅栏的同一侧。(如果有牛群在栅栏所在的直线上,那么栅栏是没用的),Farmer John 将会多次询问你一个栅栏是否有用,如果这个栅栏是有用的,需要输出 `YES`,反之输出 `NO`。 另外,Farmer John 也可能会带来一些新的奶牛加入这个牛群。一头牛加入之后,以后的所有询问中,这头牛也需要与其它的牛在栅栏的同一侧。

输入输出格式

输入格式


第一行,两个正整数 $n,q$,表示初始时牛群的数量与询问个数; 后 $n$ 行,每行两个整数 $x,y$,表示一个牛群的初始位置; 后 $q$ 行,每行多个整数,表示一次询问,询问的格式如下: - 1 $x$ $y$:表示一个新的牛群加入了牧场,驻留在 $(x,y)$ 上; - 2 $A$ $B$ $C$:表示 Farmer John 询问栅栏 $Ax+By=C$ 是否有用。

输出格式


对于每个 $2$ 类型的询问,如果栅栏有用,输出 `YES`,否则输出 `NO`。

输入输出样例

输入样例 #1

3 4 
0 0 
0 1 
1 0 
2 2 2 3 
1 1 1 
2 2 2 3 
2 0 1 1 

输出样例 #1

YES 
NO 
NO 

说明

直线 $2x+2y=3$ 使得初始的三个牛群都在同侧;然而在该栅栏另一侧的牛群 $(1,1)$ 的加入使得它没有用了。 直线 $y=1$ 没用因为牛群 $(0,1)$,$(1,1)$ 恰好在它上面。 --- 对于 $100\%$ 的数据,保证 $1\leq n\leq 10^5$,$1\leq q\leq 10^5$,所有牛群的坐标都各不相同且满足 $-10^9\leq x,y\leq 10^9$,$-10^9\leq A,B\leq 10^9$,$-10^{18}\leq C\leq 10^{18}$。 数据保证不存在栅栏满足 $A=B=0$。