At first I thought it might require something like voronoi diagram since the straightforward solution is to find the nearest mine for each zombie. However I have never implemented voronoi diagram and the O(nlogn) time algorithm to construct voronoi diagram seems tricky. Looking at the contest, several teams solved it so there has to be other ways as not many people have implemented voronoi diagram.
Looking at the grid column by column, we know that for each cell in a given column j, for each row i we need only remember the nearest M from left, if our nearest M at row k is from left. We can also find the nearest M from the right. The better of the two is our nearest M for cell(i,j) at row k. So for each column j=0 to w-1, we can compute an array of near[0..h-1] such that near[k] is dist from the nearest M at row k. We can compute this for all columns j, so we have a matrix near[0..h-1][0..w-1],
near[i][j] is the column difference from nearest M at row i to column j.
It takes only O(n^2) time to compute near[][] so we are good so far.
Now we binary search the smallest radius that covers all zombies. The max is w+h, min is 0. And since w<=2000 and h<=2000, for a relative error of 1.0e-6, we need only iterate 30 times since 2^30=10^9. Now we deal with each radius. Given a radius, we need to check whether it is enough to cover all zombies. Again we look at each column. If some M is to cover anything in this column, it has to be a near[i][j]. So for each near[k][j], k=0 to h-1, we calculate the interval that near[k][j] covers at column[j], and we can use a vector
In the end we have a decision to make, more iteration gives better precision but might TLE. Tried 20 and 25, both got WA, so 30 is the next thing to try and got AC finally.
In the original problem number of zombie and mines are limited to 10^5 so might be slightly easier to deal with.
No comments:
Post a Comment