레이팅 미적용농부 존은 소들의 이동을 제한하기 위해 직선 모양의 울타리를 어디에 세울지 결정하는 데 도움이 필요하다. 그는 여러 후보 울타리 위치를 검토하며 각 위치가 사용 가능한지 판단해야 한다. 울타리는 모든 소가 울타리의 같은 쪽에 있을 때 사용 가능하다. 울타리 위에 정확히 놓인 소가 있으면 그 울타리는 사용할 수 없다.
또한 FJ는 때때로 소 떼에 새로운 소를 들여올 수 있다. 새로운 소가 합류하면, 그 이후의 모든 울타리 질의에서는 울타리가 사용 가능하려면 그 소도 나머지 소 떼와 같은 쪽에 있어야 한다.
첫째 줄에 N (1 <= N <= 100,000)과 Q (1 <= Q <= 100,000)가 주어진다. 다음 N개의 줄 각각에 소의 위치를 나타내는 두 정수 x와 y가 주어진다. 나머지 Q개의 줄에는 질의가 주어진다: "1 x y"는 (x, y)에 새로운 소를 추가하고, "2 A B C"는 직선 Ax + By = C로 표현되는 울타리를 검사한다. 위치는 -10^9 <= x, y <= 10^9를 만족하고, 울타리 질의는 -10^9 <= A, B <= 10^9, -10^18 <= C <= 10^18을 만족하며, A=B=0인 경우는 없다.
각 울타리 질의마다 울타리가 사용 가능하면 "YES", 그렇지 않으면 "NO"를 출력한다.
fencing.in · 출력을 쓸 파일 fencing.out3 4
0 0
0 1
1 0
2 2 2 3
1 1 1
2 2 2 3
2 0 1 1YES
NO
NOOutput details: 2x+2y=3 leaves the initial 3 cows on one side (YES); after (1,1) joins it is no longer usable (NO); the line y=1 passes through cows (NO).
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > February > Gold