You are given a grid square of size R x H (R & H <= 10^9). You are also given N special points (N <= 5000). Each of the N special points has a different power Ri (R <= 10^9) associated with it. Each of these points can influence all points of the grid within a manhattan distance of R (if the manhattan distance between the special point and any other point is <= Ri, it will be influenced). Find out how many points are totally influenced in the grid.↵
↵
I thought about some sort of coordinate compression + Line Sweep algorithm + dp but could not get it through. I also tried converting points into x + y & x — y + coordinate compression + BIT but could not get any ideas. Please help. I am so stuck! Thanks in advance.
↵
I thought about some sort of coordinate compression + Line Sweep algorithm + dp but could not get it through. I also tried converting points into x + y & x — y + coordinate compression + BIT but could not get any ideas. Please help. I am so stuck! Thanks in advance.
