Fencing the Herd
골드 II의견: 0
Farmer John needs help deciding where to build a fence in the shape of a straight line to restrict the movement of his cows. He considers several possible fence locations and needs to determine which are usable, where a fence is 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.
Additionally, FJ may occasionally bring new cows into the herd. When a new cow joins, all fence queries from that point onward require her to be on the same side as the rest of the herd for the fence to be usable.
Line 1: N (1 <= N <= 100,000) and Q (1 <= Q <= 100,000). The following N lines each contain two integers x and y giving the position of a cow. The remaining Q lines contain queries: "1 x y" adds a new cow at (x, y); "2 A B C" tests a fence described by the line Ax + By = C. Positions satisfy -10^9 <= x, y <= 10^9; fence queries satisfy -10^9 <= A, B <= 10^9, -10^18 <= C <= 10^18, never A=B=0.
For each fence query, output "YES" if the fence is usable, otherwise "NO".
fencing.infencing.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
평가 및 의견
Fencing the Herd
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Fencing the Herd