### mjguru's blog

By mjguru, history, 12 months ago, ,

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.

 » 12 months ago, # |   0 Auto comment: topic has been updated by mjguru (previous revision, new revision, compare).
 » 12 months ago, # |   0 Auto comment: topic has been updated by mjguru (previous revision, new revision, compare).
 » 12 months ago, # | ← Rev. 2 →   +8 First convert coordinates to x + y and x — y when you need to find area of union of squares. it is a standart task, you can find solution description at topcoder: Line sweep tutorial
•  » » 12 months ago, # ^ |   0 Could you elaborate. What would be the edge size? Where will be the corners?
•  » » » 12 months ago, # ^ |   +3 ok. at first you have coordinates x, y |x-a|+|y-b|<=twhen if you solve this, you will have a square rotated by 45 degrees. and 4 cornersok, lets rotate it by 45 degress.
•  » » » » 12 months ago, # ^ | ← Rev. 3 →   0 I do not think that is correct. Consider just one special point at 10, 10 of power 1. It will influence the following points: (10, 10), (10, 9), (10, 11), (9, 10), (11, 10). However, by your method, it will be converted into a rectangle of width 2 whose area will be four. Please correct me if I am wrong or have misunderstood you
•  » » » » » 12 months ago, # ^ |   0 you need another function of area inside line sweep
•  » » » » » » 12 months ago, # ^ |   0 Could you explain with an example? I am having a really hard time understanding your approach.
 » 12 months ago, # |   0 Auto comment: topic has been updated by mjguru (previous revision, new revision, compare).
 » 12 months ago, # |   -19 Hey this is very nice and interesting