Author: Ildar Gainullin
Tester: Lewin Gan
Editorialist: Misha Chorniy
Difficulty:
Medium-Hard
Pre-Requisites:
Set
Problem Statement
There is a set of points in 2D, we need to process next queries. Add/erase point in the set of points, and output the square of distance between pair of nearest points. If size of set less than 2, output 0. Initially the set is empty, coordinates of points lies in a range from 1 to 500.
Subtasks 1 and 2
Number of queries is less than 2500, we can store all paires squares of distances in set. Adding/erasing point into the set equivalent adding/erasing squares of distance to all points which lies in the set. After that we need to print minimal element in the set. Complexity will be O(Q^2 log Q)
points = []
dist = {}
for i=1..Q
c,x,y=read()
if c == '+':
for i in points:
dist.insert(square(points[i], (x,y)))
points.add((x,y))
else:
points.erase((x,y))
for i in points:
dist.erase(square(points[i], (x,y)))
if !dist.empty():
print dist.minElement()
else:
print 0
Subtask 3
We can use divide-and-conquer by queries to solve this problem, consider problem only with adding queries. Suppose that we are adding point (x, y) into set and ans is the current minimal square of distance between two points in the set, if set contains less than 2 points, assume ans = 10^9. We need to check only those points (dx, dy), which makes new answer less than ans. Let’s maintain for each x the set of y - coordinates of points which has the same x. If we need to update answer for a point (x, y), let’s iterate over dx, and check two points(if they exists), point (dx, dy1), where dy1 >= y and (dx, dy2), where dy2 < y we can find them in O(log 500) and update the answer. We don’t see, if (dx -x)^2>ans, because it has no sense to update the answer. When a number of points in the set are more then a couple of thousands, ans won’t be big. How to process erase queries? At first, we will solve this problem in offline, i.e initially read all queries and after that process it. At second, for each time of adding a point, let’s find nearest time of erasing this point, if this point will be in the set to the end, assume that we erase it in moment of time Q+1, after that each point has an interval [L; R], where it is alive(i.e contains in the set). One point can have several intervals. intervals contains all intervals for points. Look at the following code:
solve(L, R, intervals, ans = 1e9) {
int M = (L + R) / 2
newIntervals = []
for cint in intervals
if cint.end < L OR cint.begin > R //Point which is added in moment of time cint.begin won't be used in queries in a range from L..R, because it erased in the moment of time cint.end
continue
if cint.begin <= L AND cint.end > R //Point will be used for any query in a range L..R, we add it
AddPoint(x[cint.begin], y[cint.begin], newAns) //adding point and recalcuating ans
else: //Otherwise we will process this point somewhere deeper, number of such adding is O(R - L) in array newIntervals
newIntervals.add(cint)
if (L != R) {
solve(L, M, newIntervals, newAns)
solve(M + 1, R, newIntervals, newAns)
} else
res[L] = newAns
rollback() //rollback all changes which were done in this call of function with AddPoint
}
solve(1, Q, 1e9)
Total complexity of this algorithm is O(Q * log Q * 500 * log 500) but with very small constant.
Solution:
Setter’s solution can be found here
Tester’s solution can be found here
Please feel free to post comments if anything is not clear to you.