Need help on a manhattan distance problem

Revision en4, by mjguru, 2017-04-21 19:38:57

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.

Edit: I meant lattice points while referring to points in all cases.

Tags manhattan distance, dp, line sweep

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English mjguru 2017-04-21 19:38:57 74
en3 English mjguru 2017-04-21 16:47:09 145
en2 English mjguru 2017-04-21 16:44:57 18
en1 English mjguru 2017-04-21 16:44:07 610 Initial revision (published)