A1053. Fencing the Herd--Gold
编程题
省选/NOI-
知识点
题目描述
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.
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.
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".
"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
输出 #1
YES NO 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_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._
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_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._