P3122 [USACO15FEB] Fencing the Herd G

Farmer John needs your help deciding where to build a fence shaped as an infinitely long straight line to restrict the movement of his cows. He has selected several candidate positions for building the fence, and you need to determine which fences are useful. A fence is useful if and only if all cows lie on the same side of the fence. If any cow lies exactly on the fence line, then the fence is useless. Farmer John will ask you multiple times whether a fence is useful; for each query, output YES if the fence is useful, otherwise output NO. Additionally, Farmer John may bring in new cows to join the herd. After a cow joins, it must be considered in all subsequent queries and must also lie on the same side of the fence as the other cows.

The first line contains two positive integers $n, q$, the initial number of cows and the number of queries. The next $n$ lines each contain two integers $x, y$, the initial positions of the cows. The next $q$ lines each describe a query in one of the following formats: - 1 $x$ $y$: a new cow joins the pasture at $(x, y)$. - 2 $A$ $B$ $C$: Farmer John asks whether the fence $Ax + By = C$ is useful.

For each query of type $2$, output YES if the fence is useful, otherwise output NO.

The line $2x + 2y = 3$ places all three initial cows on the same side; however, adding the cow $(1, 1)$ on the other side makes it useless. The line $y = 1$ is useless because cows $(0, 1)$ and $(1, 1)$ lie exactly on it. --- Constraints. For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq q \leq 10^5$, all cows have distinct coordinates and satisfy $-10^9 \leq x, y \leq 10^9$, $-10^9 \leq A, B \leq 10^9$, $-10^{18} \leq C \leq 10^{18}$. It is guaranteed that there is no fence with $A = B = 0$. Translated by ChatGPT 5