Fencing the Herd#11184
Farmer John needs your help deciding where to build a straight-line fence to restrict the movement of his cows. He has considered several possible fence locations and needs your help determining which ones are usable. A fence is considered usable if all cows are strictly on the same side of the fence; a fence is not usable if any cow lies directly on it.
FJ will make a number of queries about possible fence locations. For each query, output if the corresponding fence is usable and otherwise.
Additionally, FJ may occasionally add new cows to the herd. From the moment a new cow joins the herd, every subsequent fence query must also have that cow on the same side of the fence as all the other cows for the fence to be considered usable.
The first line contains two integers n~(1 \le n \le 10^5) and q~(1 \le q \le 10^5), representing the initial number of cows in the herd and the number of queries, respectively.
The following lines describe the initial state of the herd. Each line contains two space-separated integers and , giving the position of a cow.
The remaining lines contain queries that either add a new cow to the herd or test a fence for usability.
A query of the form "1 x y" adds a new cow at position .
A query of the form "2 A B C" asks whether the fence described by the equation Ax + By = C is usable.
All cow positions are distinct throughout the entire input and satisfy -10^9 \le x, y \le 10^9. The fence parameters satisfy -10^9 \le A, B \le 10^9 and -10^{18} \le C \le 10^{18}. No fence query has A = B = 0.
For each fence query, print "" if the fence is usable and "" otherwise.
The line 2x + 2y = 3 initially places all cows on the same side of the fence. However, after the cow at joins the herd, she lies on the opposite side, so the fence is no longer usable.
The line y = 1 is not usable because the cows at and lie directly on the fence.
Example 1