Placeholder

#3921

Fencing the Herd 2초 256MB

문제

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.


[Problem credits: Richard Peng, 2015]


입력

The first line of input contains N (1<=N<=100,000)(1 <= N <= 100,000) and Q (1<=Q<=100,000)(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 "1xy1 x y" means that a new cow has been added to the herd at position (x,y)(x, y). A line of the form "2ABC""2 A B C" indicates that FJ would like to test a fence described by the line Ax+By=CAx + By = C.

All cow positions will be unique over the whole data set and will satisfy (−109<=x,y<=109)(-10^9 <= x, y <= 10^9). Additionally the fence queries will satisfy −109<=A,B<=109-10^9 <= A, B <= 10^9 and −1018<=C<=1018-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".


예제1

입력
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

The line 2x+2y=32x + 2y = 3 leaves the initial 3 cows on the same side. However the cow (1,1)(1, 1) is on the other side of this fence making it no longer usable after she joins the herd. The line Y=1Y = 1 cannot be used because the cows (0,1)(0, 1) and (1,1)(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_base::sync_with_stdio(false)" to read input faster. Java users should avoid using java.util.Scanner. Do not flush output (e.g. using std::endl) after each query.


출처

USACO 2015 February Gold


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.