Fencing the Herd
Fencing the Herd
Farmer John needs your help deciding where to build a fence in the shape of a straight line to help restrict the movement of his cows. He has considered several possible fence locations and needs your help to determine which of these are usable, where a fence is considered usable if all of the cows are on the same side of the fence. A fence is not usable if there is a cow that lies directly on it. FJ will be asking you a number of queries regarding possible fence locations; a query should be answered "YES" if it corresponds to a usable fence location, "NO" otherwise.
Additionally, FJ may occasionally bring new cows into the herd. When a new cow joins the herd, all fence queries from that point onward will require her to be on the same side of a fence as the rest of the herd for the fence to be usable.
Input
The first line contains n (1 ≤ n ≤ 105
) and q (1 ≤ q ≤ 105
). These give the number of cows initially in the herd and the number of queries, respectively.
The following n lines describe the initial state of the herd. Each line will contain two space separated integers x and y giving the position of a cow.
The remaining q lines contain queries either adding a new cow to the herd or testing a fence for usability. A line of the form "1 x y" means that a new cow has been added to the herd at position (x, y). A line of the form "2 A B C" indicates that FJ would like to test a fence described by the line Ax + By = C.
All cow positions will be unique over the whole data set and will satisfy (-109
≤ x, y ≤ 109
). Additionally the fence queries will satisfy -109
≤ A, B ≤ 109
and -1018
≤ C ≤ 1018
. No fence query will have A = B = 0.
Output
For each fence query, output "YES" if the fence is usable. Otherwise output "NO".
Example
The line 2x + 2y = 3 leaves the initial 3 cows on the same side. However the cow (1, 1) is on the other side of this fence making it no longer usable after she joins the herd. The line y = 1 cannot be used because the cows (0, 1) and (1, 1) lie directly on it.
3 4 0 0 0 1 1 0 2 2 2 3 1 1 1 2 2 2 3 2 0 1 1
YES NO NO