Pre-requisites: Binary heap, Geometry, Manhattan distance
Let’s consider a set of points S. Your task is to implement a data structure that can process the following queries efficiently:
- “+ X Y” - add a new point P with coordinates (X, Y) to S;
- “- N” - remove the point that was added during the N’th adding query from S;
- “? X Y” - calculate the maximal Manhattan distance between a point P with coordinates (X, Y) and any point from S.
It’s required to implement an on-line solution, i.e. which processes queries in the order of their appearance.
Let’s transform the formula of Manhattan distance a little bit:
dist(P1, P2) = |X1 - X2| + |Y1 - Y2| = max(X1 - X2, X2 - X1) + max(Y1 - Y2, Y2 - Y1) = max((X1 + Y1) - (X2 + Y2), (X1 - Y1) - (X2 - Y2), (-X1 + Y1) - (-X2 + Y2), (-X1 - Y1) - (-X2 - Y2)) = max(f1(P1) - f1(P2), f2(P1) - f2(P2), f3(P1) - f3(P2), f4(P1) - f4(P2)), where
- f1(P) = X + Y;
- f2(P) = X - Y;
- f3(P) = -X + Y;
- f4(P) = -X - Y.
In other words, dist(P1, P2) equals to the maximum of four values, that don’t contain abs() function anymore.
It’s time to make the key observation of this problem:
Let’s suppose that we are to find the maximal Manhattan distance between a point P and any point from S. The key fact is that there are only four candidates to be the most distant one: the ones with the maximal f1(P), f2(P), f3(P) and f4(P) from S.
So, we can maintain S as four separate binary heaps H1, H2, H3 and H4, each point of S belongs to each of Hi. The points are ordered according to fi(P) in heap Hi.
Now, if we want to add a new point to S, then we add it to each of Hi. If we want to calculate the maximal Manhattan distance between a point P and any point from S, then we find the most distant point from S(as the most distant one among ones with the maximal f1(P), f2(P), f3(P) and f4(P)).
What about removing points from S? As we know, a binary heap doesn’t provide any kind of removing except removing from the top of the heap. But that’s OK, we won’t remove them for real until they affect the answers. We can just mark removed points somehow and every time, when a ‘removed’ point is on the top of one of the binary heaps, we remove it from this heap for real. The reason why we are not removing a point from S until it is not on the top is that such a point doesn’t affect the answers, since only the ones on the tops are considered as candidite for being the most distant point every time we are interested to know that information.
The total complexity of the solution is O(Q log Q).
Please, check out Setter’s and Tester’s solutions for your better understanding.
Setter’s Solution: link
Tester’s Solution: link