A1039.Fencing the Herd--Gold

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.

The first line of input contains N (1 <= N <= 100,000) and Q (1 <= Q <=
100,000) separated by a space. 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
(-10^9 <= x, y <= 10^9). Additionally the fence queries will satisfy -10^9 <=
A, B <= 10^9 and -10^18 <= C <= 10^18. No fence query will have A = B = 0.

For each fence query, output "YES" if the fence is usable. Otherwise output
"NO".

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.
Warning: The I/O for this problem is fairly large. C++ users may consider
using scanf or the line "ios_basesync_with_stdio(false)" to read input
faster. Java users should avoid using java.util.Scanner. Do not flush output
(e.g. using stdendl) after each query.