Олимпиадный тренинг

Задача 27299. Fencing the Herd


Задача

Темы:
Farmer John needs your help. He decided to build a straight line fence to restrict the movement of his cows. He is considering several options for placing a fence and wants to determine the most suitable one with your help. A suitable option is when all the cows are on the same side of the fence. A fence is not considered suitable if at least one cow is located on the fence. The FD will ask you questions about the fence options, to which you must answer YES if the fence is suitable and NO otherwise.
 
In addition, the FD can add new cows to the herd. Once a cow is added, it should be on the same side of the fence as all other cows.
 
Input 
The first line of input contains N (1 <= N <= 100000) and Q (1 <= Q <= 100000) separated by a single space. These are, respectively, the initial number of cows in the herd and the number of requests.
The following N lines describe the starting position of the herd. Each line contains two integers x and x (separated by a space) representing the position of the next cow.
The remaining Q lines contain requests that either add a new cow to the herd or check the fence for applicability. A string like 1 x y means that a new cow is added to the herd at position x y. A line like 2 A B C means that the FD wants to check the fence described by the line Ax+By =C.
All cow positions are unique (-109 <= x, x <= 109). Also, -109 <= A, B <= 109 and -1018 <= C <= 10 18. There will never be a hedge with A = B = 0.
 
Output
For each fence, print YES if it matches and NO otherwise.
 
Input Output
3 4
0 0
0 1
10
2 2 2 3
1 1 1
2 2 2 3
2 0 1 1
YES
NO
NO
 
A straight line 2x + 2y = 3 leaves the original 3 cows on one side. However, the cow (1,1) is on the other side, so after adding it, such a fence no longer fits. The line Y=1 doesn't work because cows (0,1) and (1,1) are on it.
 
Warning: I/O for this task is very large. In C++ you can use scanf or ios_base::sync_with_stdio(false). In Java, don't use java.util.Scanner. Don't flush output (eg? using std::endl) after each request.