Mixture
Contest: Baltic Olympiad in Informatics 2020, Day 1 (IOI, Unofficial Mirror Contest, Unrated)
Difficulty rating: 2900
Tags: *special, data structures, geometry, math, sortings

Serge, the chef of the famous restaurant "Salt, Pepper & Garlic" is trying to obtain his first Michelin star. He has been informed that a secret expert plans to visit his restaurant this evening.

Even though the expert's name hasn't been disclosed, Serge is certain he knows which dish from the menu will be ordered as well as what the taste preferences of the expert are. Namely, the expert requires an extremely precise proportion of salt, pepper and garlic powder in his dish.

Serge keeps a set of bottles with mixtures of salt, pepper and garlic powder on a special shelf in the kitchen. For each bottle, he knows the exact amount of each of the ingredients in kilograms. Serge can combine any number of bottled mixtures (or just use one of them directly) to get a mixture of particular proportions needed for a certain dish.

Luckily, the absolute amount of a mixture that needs to be added to a dish is so small that you can assume that the amounts in the bottles will always be sufficient. However, the numeric values describing the proportions may be quite large.

Serge would like to know whether it is possible to obtain the expert's favourite mixture from the available bottles, and if so—what is the smallest possible number of bottles needed to achieve that.

Furthermore, the set of bottles on the shelf may change over time as Serge receives new ones or lends his to other chefs. So he would like to answer this question after each such change.

For example, assume that expert's favorite mixture is $$$1:1:1$$$ and there are three bottles of mixtures on the shelf:

$$$$$$ \begin{array}{cccc} \hline \text{Mixture} & \text{Salt} & \text{Pepper} & \text{Garlic powder} \\ \hline 1 & 10 & 20 & 30 \\ 2 & 300 & 200 & 100 \\ 3 & 12 & 15 & 27 \\ \hline \end{array} $$$$$$ Amount of ingredient in the bottle, kg

To obtain the desired mixture it is enough to use an equivalent amount of mixtures from bottles 1 and 2. If bottle 2 is removed, then it is no longer possible to obtain it.

Write a program that helps Serge to solve this task!

Input format:
The first row contains three non-negative integers $$$S_f$$$, $$$P_f$$$ and $$$G_f$$$ ($$$0 \leq S_f, P_f, G_f$$$; $$$0 < S_f+P_f+G_f \leq 10^6$$$) describing the amount of salt, pepper and garlic powder in the expert's favourite mixture. For any real $$$\alpha>0$$$, $$$(\alpha{S_f}, \alpha{P_f}, \alpha{G_f})$$$ also is an expert's favourite mixture.

In the second row, there is a positive integer $$$N$$$ (number of changes on the shelf, $$$N \leq 100\,000$$$). You should assume that initially the shelf is empty.

Each of the next $$$N$$$ rows describes a single change on the shelf:

- If a new bottle is added, the row contains capital letter $$$A$$$ followed by three non-negative integers $$$S_i$$$, $$$P_i$$$ and $$$G_i$$$ ($$$0 \leq S_i, P_i, G_i$$$; $$$0 < S_i+P_i+G_i \leq 10^6$$$) describing the amount of salt, pepper and garlic powder in the added bottle. Added bottles are numbered consecutively by unique integers starting from $$$1$$$, that is, the $$$i$$$-th bottle corresponds to the $$$i$$$-th added bottle in the input data.
- If a particular bottle is removed from the shelf, the row contains capital letter $$$R$$$ followed by the integer—the bottle number $$$r_i$$$. All values $$$r_i$$$ in the removals are unique, $$$r_i$$$ never exceeds total number of bottles added thus far.

Output format:
Output $$$N$$$ rows. The $$$j$$$-th row ($$$1 \leq j \leq N$$$) should contain the number $$$x_j$$$, the smallest number of bottles needed to prepare a mixture with the expert's favourite proportions of salt, pepper and garlic powder using the bottles available after the first $$$j$$$ changes on the shelf, or $$$0$$$ if it is not possible.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
Scoring:
Subtasks:

1. (13 points) $$$N \leq 50$$$, $$$0 < S_i+P_i+G_i \leq 10^2$$$
2. (17 points) $$$N \leq 500$$$, $$$0 < S_i+P_i+G_i \leq 10^3$$$
3. (30 points) $$$N \leq 5000$$$, $$$0 < S_i+P_i+G_i \leq 10^4$$$
4. (40 points) No further constraints

Pay attention that in the example, bottles $$$1$$$ and $$$3$$$ contain the same proportions of salt, pepper and garlic powder.

Example input:
1 2 3
6
A 5 6 7
A 3 10 17
R 1
A 15 18 21
A 5 10 15
R 3

Example output:
0
2
0
2
1
1

Editorial:
The crux of solving this problem is to think about it from a geometric perspective and discover a couple of properties, afterwards it's a matter of implementing efficient ways / data structures to process the queries accordingly.
There are a couple of possible approaches, but it seems easiest to translate it to a 2D geometry problem. We first translate all mixtures - the target mixture and the bottles - to 2D points in the following way: given a mixture with proportions $$$(S, P, G)$$$ we transform it to a point $$$(x, y) = (S/(S+P+G), P/(S+P+G))$$$. Intuitively $$$x$$$ and $$$y$$$ are the relative amounts of salt and pepper, respectively, in the mixture. Now scaling the proportion values (i.e., multiplying $$$S$$$, $$$P$$$, $$$G$$$ with the same coefficient, which describes an identical mixture) keeps $$$(x, y)$$$ constant. Mixing two or more bottles ends up combining these 2D points (or vectors) with positive weights the sum of which is 1.
Having that, we consider these lemmas (proofs are left as an exercise):
Lemma 1. If a bottle point matches the target point, the target mixture can be obtained using only that one bottle.
Lemma 2. If the line segment defined by two different bottle points contains the target point, the target mixture can be obtained using those two bottles.
Lemma 3. If the triangle defined by three different bottle points contains the target point, the target mixture can be obtained using those three bottles.
Lemma 4. If the target point is not contained by any triangle defined by three different bottles, the target mixture cannot be obtained.
Based on these properties we can define the following general algorithm:
1. Maintain the set of points.
2. At each step, check the state to find the answer: 2a. If there is a point matching the target point $$$\Rightarrow$$$ 1. 2b. Otherwise, if there is a pair of points whose line segment contains the target point $$$\Rightarrow$$$ 2. 2c. Otherwise, if there is a triplet of points whose triangle contains the target point $$$\Rightarrow$$$ 3. 2d. Otherwise $$$\Rightarrow$$$ 0.
Subtask 1 ($$$N \leq 50$$$)
At each step we can simply check each point / pair of points / triplet of points to see if we have case (2a), (2b), or (2c). This takes $$$O(N)$$$ / $$$O(N^2)$$$ / $$$O(N^3)$$$ time for each query, so the total time complexity to process all queries is $$$O(N^4)$$$.
Complexity: $$$O(N^4)$$$
Subtask 2 ($$$N \leq 500$$$)
Full search on all points / pairs of points is still feasible here. We need to speed-up the case (2c): checking the triangles. Here the key observation is that instead of considering all triangles individually we can check whether the target point is inside the convex hull defined all bottle points; namely, if the target point is inside the convex hull there exists at least one triplet of bottle points the triangle of which contains the target point, and if it is outside the hull no such triplet exists. It's possible to build the convex hull and check if the target point is inside it in time $$$O(N \log N)$$$, but for this subtask a sub-optimal approach up to $$$O(N^2)$$$ is also good enough.
Complexity: $$$O(N^3)$$$
Subtask 3 ($$$N \leq 5000$$$)
Full search on all single points still feasible. To check triplets we do the same convex hull approach as in the previous subtask, but we have to use the optimal $$$O(N \log N)$$$ method this time. For pairs of points we need something better. If we fix a point as one end of the line segment, to have the target point on the segment we know that the other point has to be exactly opposite from the first point relative to the target point (direction-wise, the distance doesn't matter). In other words, after fixing the first point we know exactly at what angle the second point should be (with respect to the target point). So if we have a data structure that we can store points in and test for existence by angle (e.g., using tangent value), we can load all current points in it and then go through each bottle point and quickly check whether an opposite point currently exists. If there is never an opposite point, it means we don't have any line segment containing the target point, and vice versa. It can be done in $$$O(N \log N)$$$ for each query.
Complexity: $$$O(N^2 \log N)$$$
Subtask 4 ($$$N \leq 10^5$$$)
For the previous subtasks we were answering each query completely independently. For the full solution we aim for a $$$O(\log N)$$$ time for each query so we need to find a way to maintain the state of points through time so that we can update the state (add / remove bottles) and check the current answer quickly for each query. Let's look at all cases (single point, pair, triplet) separately:
a. For single point checks we can keep the points in a structure that let's us add/remove/find in $$$O(\log N)$$$ time. We can also just maintain a counter for matching bottles that we increase/decrease whenever we add/remove a point that matches the target point - then at any step the answer is 1 if the counter is greater than zero.
b. For solving the line segment case we go back to the previous idea. If we have all bottle points stored in an appropriate data structure, we need $$$O(N \log N)$$$ time per query to check whether there exist opposite points ($$$N$$$ points, $$$O(\log N)$$$ check if an opposite point exists), which is too slow. However, we can maintain a counter for the total number of pairs of points that are opposite to each other (with respect to the target point) within the set of all current points, and update it after each query. Then, similarly to the single point case, the answer is 2 if this counter is greater than zero. To achieve this we need to maintain a data structure that stores all angles of points (e.g., tangent value) and checks for (and allows to update) the number of elements with a certain value currently stored. This can be done in $$$O(\log N)$$$ time for each operation.
c. For the triplet case we can use the same convex hull idea, but we need a dynamic version that we can update query-to-query (add/remove points) and test whether the target point is inside it. This can be done with an amortized time of $$$O(\log N)$$$ per query. However, we don't really need to construct the exact convex hull itself, we just need a way to tell whether the (single fixed) target point is inside of it. If we order all points around the target point by angle, then it's enough to check whether all angles between consecutive points are less than 180 degrees. If that's not the case (i.e., some two consecutive points are more than 180 degrees apart) then the target point is outside the hull (and the answer is 0), otherwise inside (answer 3). We need to maintain the points ordered in such a way by adding/removing points for each query, and be able to check for angles bigger than 180 degrees. There are various ways how to do this technically, and it can be done in $$$O(\log N)$$$ time per query.
Complexity: $$$O(N \log N)$$$.
Final notes
1. In the end for the final solution all cases can be handled using the same data structure that stores the points/angles, so the solution becomes relatively concise.
2. This problem requires divisions. You can simply use floating point numbers, but there is a risk of making the wrong discrete decisions due to floating point imprecision. The correct way here is to work with rational number, i.e., store and operate with values as numerators and denominators ($$$p/q$$$). However, you still have to be careful to not cause overflows. Note that subtasks have varying constraints on the proportion values, which allows more freedom in operations without causing overflows. The full problem has a constraint of $$$10^6$$$, and it is possible to implement a solution that only multiplies these values once so we use 2nd order values. (3rd order is also tolerated, but more typical careless approaches that yield 4th or 8th degree values are penalized in later subtasks).