You are given a grid square of size R x H (R & H <= 10^9). You are also given N points (N <= 5000). Each of the N points has a power R (R <= 10^9) associated with it. Each of these points can influence all points within a manhattan distance of R. Find out how many points are nettotally 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.
