Observing the objective function

In order to find \(\displaystyle \max_{(x,y) \in S}\{Ax + By\}\) fast, we will now observe what kind of function \(Ax + By\) is.

By the visualization, we can see that, the more it advances in the direction of vector \((A, B)\), the larger the value gets. It can be also understood by the fact that \(Ax + By\) is an inner product of vector \((A, B)\) and vector \((x, y)\). Therefore, \(\displaystyle \max_{(x,y) \in S}\{Ax + By\}\) takes maximum at the point that is the furthest in the direction of \((A, B)\).

If no points are added

First, we assume that \(S\) has always \(N\) points and never be updated, and we are given many queries that asks \(\displaystyle \max_{(x,y) \in S}\{Ax + By\}\).

By the observation above, we can see that \(\displaystyle \max_{(x,y) \in S}\{Ax + By\}\) cannot be maximum outside \(S\), i.e. it can be maximum only at the points that forms the convex hull of \(S\). Also, when the points on the convex hull of \(S\) is lined up, the objective function is monotonic. Therefore, by precomputing the convex hull of \(S\), the maximum value can be found in an \(O(\log N)\) time per query with trinary search or golden-section search.

If points are added

Now, let’s consider the original problem. Since the points are added, we have to manage the convex hull of \(S\) dynamically. By managing the sequence of points on the convex hull by a balanced binary search tree, points can be added in an \(O(\log Q)\) time per query, so the problem can be solved in a total of \(O(Q \log Q)\) time.

However, there is an issue in this method: in many languages, balanced binary search trees in standard libraries are insufficient; we have to prepare an advanced balanced binary search tree by our own.

Some balanced binary search trees like __gnu_pbds::tree are capable of finding the \(n\)-th element, which enable us to solve the problem in a total of \(O(Q (\log Q)^2)\) time, so we may use them to solve it.

Regarding as segment queries

Let’s seek an alternative way.

We can regard the \(i\)-th query as an query against the segment from Point \(1\) through Point \(i\). When it comes to query-for-segment problem, segment trees work. By finding the convex hull for each segment on the segment tree, we can find the maximum value by computing against \(O(\log Q)\) convex hulls and finding their maximum value, so the problem can be solved in a total of \(O(Q (\log Q)^2)\) time.

Bonus: solve the problem in \(O(Q \log Q)\) time without using balanced binary search trees.

Sample code (C++)

Sample code (Python)