Given a growing set of (A,B) pairs, decide each day whether the new pair is dominated by or lies on the segment between two existing points.
Hard8GeometryBinary searchSortingGreedyNo attempts yetTime limit1sMemory limit512 MBTaeyoung is a scientist who runs experiments with strange solutions in his own small lab. The lab holds N strange solutions of 1L each, and every solution contains component A and component B. Call this set of solutions S.
One day Taeyoung wants to prepare a new 1L solution for an experiment. He dislikes extra work, so he uses only these two methods.
The two components are spread evenly inside a solution. For example, if you draw 0.3L out of a 1L solution that contains 5 units of component A, the drawn part contains exactly 1.5 units of component A.
By Taeyoung's theory, more of component A and more of component B are both better for an experiment. He does not know which one matters more, so he calls a 1L solution K a bad solution when it meets the condition below.
Condition: using one of the two methods on the solutions in S, he can prepare a solution whose amount of component A and amount of component B are both at least those of K.
While preparing an experiment, Taeyoung decided that his lab has too few solutions, so he went shopping. He shops for M days, and because shopping is a bother too, he buys at most one solution per day. On day i he does this.
The decision on day i is made with every solution bought on the earlier days already inside S.
Checking each solution by hand became a bother, so Taeyoung asked you for help. Decide, for every day, whether he should buy the solution.
The first line contains the number of solutions that the lab holds at the start, N (1≤N≤105).
Each of the next N lines contains two integers ai, bi (0≤ai,bi≤109), the amount of component A and the amount of component B in the i-th solution.
The next line contains the number of shopping days, M (1≤M≤105).
Each of the next M lines contains two integers ci, di (0≤ci,di≤109), the amount of component A and the amount of component B in the solution Ki.
Print exactly M lines. On the i-th line print Yes if Taeyoung should buy the i-th solution, and No if he should not buy it.